本文共 2090 字，大约阅读时间需要 6 分钟。

迪杰斯特拉是单源最短路算法(即只能求一点，到其他任一点的最短路径，但可以加循环得到任意两点间的最短路径)，无法处理带负权变的图

算法思路图示

初始化两个集合

（1）初始化，所有距离初始化为无穷大

（2）选定点A，更新（A-A距离设为0）

（3）S集合为{A,B}，考察B的所有邻接点

为什么选定B加入集合S？

（4）S集合为{A,B,D}，在U中没有D的邻接点，不操作

（5）S集合为{A,B,D,C}，在U中没有C的邻接点，不操作

（6）S集合为{A,B,D,C,F}，更新

（7）S集合为{A,B,D,C,F,E}，在U中没有E的邻接点，不操作

（8）S集合为{A,B,D,C,F,E,G}，在U中没有G的邻接点，不操作

代码实现：

#include 
   
    #include 
    
     #define MaxVex 1000 typedef struct graph{ int vnum, ednum;//顶点的个数，边的个数 char vexs[MaxVex];  //用来存顶点数据 int edges[MaxVex][MaxVex]; //用来存边的权值（两点代替一边）}Mgraph,*Graph;void create(Graph &g){	g = (Graph)malloc(sizeof(Mgraph));	printf("请输入顶点的个数\n");	scanf("%d",&g->vnum);	printf("请输入边的个数\n");	scanf("%d",&g->ednum);		printf("请输入顶点的信息\n");	for(int i=0;i
     
      vnum;i++){		getchar();		scanf("%c",&g->vexs[i]);	}	printf("请输入边的起点，终点和权值\n");	for(int i=0;i
      
       vnum;i++)		for(int j=0;j
       
        vnum;j++) {		if(i!=j)	g->edges[i][j] = MaxVex;//初始化 		else g->edges[i][i] = 0;	}	int start,end,value;	for(int i=0;i
        
         ednum;i++){ scanf("%d%d%d",&start,&end,&value); g->edges[start][end] = value; }}void print(Graph g){ for(int i=0;i
         
          vnum;i++) for(int j=0;j
          
           vnum;j++) printf("%d ",g->edges[i][j]);} void shortPath(int *path,Graph g,int start){//start为源点的下标 bool s[g->vnum];//S集合 int dist[g->vnum]; /* 初始化的过程，只能走一步的最短路径，对应图片第一张和第二张 */ for(int i = 0;i
           
            vnum;i++){ s[i] = false;//初始化S集合，为空 dist[i] = g->edges[start][i];//初始化，源点到各个点的距离，不能直接到达值为MAX if(dist[i]
            
             vnum;i++){//除去源点，对剩下的每个点求最短路径 int min = MaxVex; int v; //用来表示点 //选择最短路径 for(int j = 0;j
             
              vnum;j++){ if(s[j]==false&&dist[j]
              
               vnum;k++){ if(s[k]==false&&(dist[v]+g->edges[v][k])
               
                edges[v][k]+dist[v]; path[k]=v; } } } for(int i = 0;i
                
                 vnum;i++) printf("%d ",dist[i]); printf("\n");} int main(){ Graph g; create(g); int path[g->vnum]; shortPath(path,g,0); for(int i=0;i
                 
                  vnum;i++) printf("%d ",path[i]); return 0;}
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://xgqen.baihongyu.com/