dijkstra算法源程序.c

来自「用C语言编的两个小小程序」· C语言 代码 · 共 36 行

Dijkstra算法源程序

#define MAX    1e+8

void dijkstra(GraphMatrix graph, Path dist[])

{  int i,j,minvex;  AdjType min;

   init(&graph,dist); /* 初始化，此时集合U中只有顶点v0*/

for(i=1; i<graph.n; i++)

{ min=MAX; minvex=0;

for(j=1; j<graph.n; j++)

        if((graph.arcs[j][j]==0) && (dist[j].length<min)) /*在V-U中选出距离值最小顶点*/

        {  min=dist[j].length;  minvex=j;  }

if(minvex==0)   break;  /* 从v0没有路径可以通往集合V-U中的顶点 */

graph.arcs[minvex][minvex]=1;   /* 集合V-U中路径最小的顶点为minvex */

for(j=1; j<graph.n; j++)       /* 调整集合V-U中的顶点的最短路径 */

{ if(graph.arcs[j][j]==1)  continue;

if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])

{  dist[j].length=dist[minvex].length+graph.arcs[minvex][j];

   dist[j].prevex=minvex;

}   }   }