Dijkstra算法求最短路径

以下是上面图以v0为起点的算法详细过程

1.标记V0 -- true[1]=1 初始化 Len[]={ 0 , INF , 10, INF , 30 , 100} 这里数组首元素未用到，数组下标从1开始表示V0以此类推

2.第一次循环与V0相邻的有V2、V4、V5，其中V2距离最短为10，标记V2，并且以V2为中间点（路径为V0->V2->Vx）更新最短路表,此时V3被更新为10+50=60,。

3.进入第二次循环，此时未被标记的有V1、V3、V4、V5,，其中从V0到这些的临时最短路分别为INF、60、30、100，从中找到最小的即V4，将V4标记为1，以V4为中间点（路径为V0->V4->Vx）更新最短路表，此时V3被更新为50，V5被更新为90。

4.进入第三次循环，此时未被标记的有V1、V3、V5，其中临时最短路分别为INF、50、90，从中找到最小的即V3，将V3标记为1，以V3为中间点（路径为V0->V4->V3->Vx）更新最短路表，此时V5被更新成60。

5.进入第四次循环，此时未被标记的有V1、V5，其中临时最短路分别为INF、60，找到V5，标记为1，以V5为中间点更新最短路表，此时没有元素被更新

6.进入第五次循环，这次循环没找到任何东西

7.退出循环，Len表中即为V0到其余各个节点的最短路径。

代码如下，要想输出最短路径，只需在加入最短路径集合是，保存一下该点即可。

#include<stdio.h>

#define LEN 6
#define INF 10000
#define Minx(a,b) ((a)>(b)?(b):(a))

int Map[LEN][LEN]; //地图原始关系，结点与结点之间存在边则为边的权值，否则为INF
int Len[LEN]; //从X到i的最短路径
int True[LEN]; //最短路径集合

int Dijkstra(int X,int Y,int N) //Dijkstra算法求两点间最短路径
{
int i,Min,Min_n,t = N;

True[X] = 1; //把起始点加入最短路径集合

for(i = 0; i < N; i++)
{
Len[i] = Map[X][i]; //初始化Len，即X点到各点的距离
}

while(t--) //循环到所有点计算一遍
{

Min = INF;
Min_n = 0;

for( i = 0; i < N; i++) //从没有加入最短路径集合的节点中找
{ // 从起点开始的最小边
if(!True[i] && Len[i] < Min)
{
Min = Len[i];
Min_n = i;
}
}
True[Min_n] = 1; //把该点加入最短路径集合

for( i = 0; i < N; i++) //以找到的最小边的节点为中间点，更新最短路径
{
Len[i] = Minx(Len[i],Len[Min_n] + Map[Min_n][i]);
}
}

return Len[Y]; //返回起始点到Y的最短路径
}

int main(void)
{
Map[0][0] = 0;
Map[0][1] = INF;
Map[0][2] = 10;
Map[0][3] = INF;
Map[0][4] = 30;
Map[0][5] = 100;

Map[1][0] = INF;
Map[1][1] = 0;
Map[1][2] = 5;
Map[1][3] = INF;
Map[1][4] = INF;
Map[1][5] = INF;

Map[2][0] = INF;
Map[2][1] = INF;
Map[2][2] = 0;
Map[2][3] = 50;
Map[2][4] = INF;
Map[2][5] = INF;

Map[3][0] = INF;
Map[3][1] = INF;
Map[3][2] = INF;
Map[3][3] = 0;
Map[3][4] = INF;
Map[3][5] = 10;

Map[4][0] = INF;
Map[4][1] = INF;
Map[4][2] = INF;
Map[4][3] = 20;
Map[4][4] = 0;
Map[4][5] = 60;

Map[5][0] = INF;
Map[5][1] = INF;
Map[5][2] = INF;
Map[5][3] = INF;
Map[5][4] = INF;
Map[5][5] = 0;

printf("%d",Dijkstra(0,3,6));

return 0;
}

Dijkstra算法求最短路径

相关推荐