dijkstra.cpp

《计算机算法基础》（华工版）关于单源点最短路径生成最短路径贪心算法；

/* 郑章孝  学号：012002013324  班级：CS0201 */
#include<stdio.h>
#include <iostream.h>
#include<stdlib.h>
//Dijkstra算法的实现
const int max=1000;     				/*max代表一个很大的数*/
void dijkstra (int v,int **cost,int n)/*求源点v到其余顶点的最短路径及其长度*/
{   int *s=new int[n],*pre=new int[n],*dist=new int[n];
	int i,min,j,k,p;
  for (i=0;i<n;i++)
    { dist[i]=cost[v][i]; /*初始化dist*/
      s[i]=0;            /*s数组初始化为空*/
      if (dist[i]<max)
        pre[i]=v;
      else pre[i]=0;
     }
  pre[v]=0;
  s[v]=1;      					/*将源点v归入s集合*/
  for (i=0;i<n;i++)
   { min=max;
     for (j=0;j<n;j++)
        if (!s[j] && (dist[j]<min))
          { min=dist[j];
           k=j;
           }       				/*选择dist值最小的顶点k+1*/
     s[k]=1;        				/*将顶点k+1归入s集合中*/
     for (j=0;j<n;j++)
        if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
          { dist[j]=dist[k]+cost[k][j];    	/*修改 V-S集合中各顶点的dist值*/
            pre[j]=k+1;         		/*k+1顶点是j+1顶点的前驱*/
            }
   }   							/*所有顶点均已加入到S集合中*/
for (j=1;j<n;j++)     				/*打印结果*/
   { 
    cout<<"V(所求源点):(V0)到V"<<j<<"结点最短路径长度="<<dist[j];
    p=pre[j];
    if(p!=0)cout<<"  其经过的结点有:";
    while (p!=0)
         { cout<<" V"<<p-1;
          p=pre[p-1];
           }
	cout<<endl;
    }
}
/*下面是为了测试dijkstra算法* 其图的实例为例3.11(其中的结点下标都减1)*
 *其实验结果见图片*                                                   */
void InitGMatrix(int **&GA,int n)   //初始化图的邻接矩阵
{
	GA=new int *[n];
	int i,j;
	for(i=0;i<n;i++)GA[i]=new int[n];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)if(i==j)GA[i][j]=0;
	else GA[i][j]=max;
}
void main()
{
	int i,j,k,e,w,n;
	int **GA;
	cout<<"输入待处理图的顶点数：";
	cin>>n;
	InitGMatrix(GA,n);
	cout<<"输入图的总边数:";
	cin>>e;
	for(k=1;k<=e;k++){
			cout<<"输入第"<<k<<"条有向有权边的起点和终点序号及权值:"<<endl;
			cin>>i>>j>>w;
			GA[i][j]=w;
		}
    dijkstra(0,GA,n);
}