本文主要是介绍最短路径（Dijsktra算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Dijsktra算法(针对无向图)：
初始时，若源点到顶点Vi有边，则D[i]为边上的权值；否则，D[i]为∞。
1）从V0出发，长度最短的最短路径是(V0 ,Vj)，即
D[j] = min{ D[i] |Vi∈V-S }
将顶点Vj加入S集合；
2) 求下一条长度最短的路径：
修改从V0出发到达集合V-S中所有顶点Vk(Vk∈V-S)的路径的长度，即
如果D[k]> D[j]+arcs[j][k] (Vk∈V-S)，
则 D[k] = D[j] + arcs[j][k]
上述路径中长度最小者（Vj）即为下一条长度最短的路径，同时将顶点Vj加入S集合（即将其从集合V-S中去掉）；
D[j]= min { D[i] | Vi∈V-S }
3) 重复2）直到求出所有顶点的最短路径。
下面上实现的代码：
#include <stdio.h>
#include <stdlib.h>const int IFINITY = 99999999;
const int N = 50;/*
测试数据
6 10
1 2 6
1 3 1
1 4 5
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
4 6 2
5 6 6
*/int map[N][N], n;
int D[N], p[N][N];void Dijsktra()
{int final[N], min, v0 = 1;int v, w, i, j, k, z;for(v = 1; v <= n; v++){final[v] = 0;D[v] = map[v0][v];for(w = 1; w <= n; ++w)p[v][w] = 0;if(D[v] < IFINITY){p[v][v0] = 1;p[v][v] = 1;}}D[v0] = 0;//集合S置初值final[v0] = 1;for(i = 1; i < n; i++) //求其余顶点的最短路径{//求其余终点的最短路径min = IFINITY;for(k = 1; k <= n; ++k)if(final[k] == 0)//顶点Vk不在集合S中if(D[k] < min){j = k;min = D[k];} // V0至Vk的路径长度更短时，更新min并用j记下顶点kfinal[j] = 1; //求出了V0到Vj的最短路径，将Vj加入集合Sfor(k = 1; k <= n; ++k)//更新其余顶点的路径及长度if(final[k] == 0 && (D[j] + map[j][k] < D[k])){D[k] = D[j] + map[j][k]; //更新Vk的路径长度for(z = 1; z <= n; ++z)p[k][z] = p[j][z];//更新Vk的路径p[k][k] = 1; //将Vk加入V0到Vk的路径中}}} int main()
{int m, s, e, w;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)map[i][j] = IFINITY;for(int j = 1; j <= m; j++){scanf("%d %d %d", &s, &e, &w);map[s][e] = map[e][s] = w;}Dijsktra();for(int k = 1; k <= n; k++){printf("第一个顶点到顶点%d的最短路径为:\n",k);for(int j = 1; j <= n; j++){if(p[k][j] == 1)printf("%d ", j);//打印路径 } printf("代价为: %d\n\n", D[k]); //打印总距离 }system("pause");return 0;
}这篇关于最短路径（Dijsktra算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
