最短路径dijkstra算法精品代码（超详解）

最短路径dijkstra算法精品代码（超详解）"/>

最短路径dijkstra算法精品代码（超详解）

还有：Floyd 算法最短路径问题精品（超详解）

先看一个视频，如果无法播放：点这里

【计算机科学速成课】Dijkstra算法视频讲解

一：简介

这个算法用于解决图中单源最短路径问题。所谓单源节点是指给定源节点，求图中其它节点到此源节点的最短路径。如下图所示：给定源节点a，求节点b到a的最短距离。

(图来自于参考资料2)

那么如何寻找？还是以上图为例：

1）初始化：设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数)，且这些节点都没被处理过。

2）从源节点出发，更新相邻节点(图中为2，3，6)到源节点的距离。然后在所有节点中选择一个最短距离的点作为当前节点。

3）标记当前节点为done(表示已经被处理过)，与步骤2类似，更新其相邻节点的距离。(这些相邻节点的距离更新也叫松弛，目的是让它们与源节点的距离最小。因为你是在当前最小距离的基础上进行更新的，由于当前节点到源节点的距离已经是最小的了，那么如果这些节点之前得到的距离比这个距离大的话，我们就更新它)。

4）步骤3做完以后，设置这个当前节点已被done，然后寻找下一个具有最小代价(cost)的点，作为新的当前节点，重复步骤3.

5)如果最后检测到目标节点时，其周围所有的节点都已被处理，那么目标节点与源节点的距离就是最小距离了。如果想看这个最小距离所经过的路径，可以回溯，前提是你在步骤3里面加入了当前节点的最优路径前驱节点信息。

看文字描述显得苍白无力，你可以结合上图，看下这个视频：.html
(dijkstra演示)，然后就清楚了。
我比较懒不想打字所以以上文字来源：
代码原创
.html
下面代码是带路径的，其他的自己可以修改。

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
#define MAX 100
#define INF 0x3f3f3f3f
int dist[MAX], path[MAX];
struct MGraph
{int edges[MAX][MAX];//邻接矩阵，记录的是两点之间的距离，也就是权值 int n,e;//顶点数和边数
}G;
void init() {memset(G.edges, INF, sizeof(G.edges));//默认为INF
}
void insert(int u, int v, int w) {G.edges[u][v] = w;//
}
void printfPath(int path[], int a){stack<int> s;//这个循环以由叶子结点到根结点的顺序将其入栈while(path[a] != -1){s.push(a);a = path[a];} s.push(a);while(!s.empty()){cout << s.top() << " ";//打印栈顶元素，实现了顶点的逆序打印s.pop(); }cout << endl;
} 
void Dijkstra(MGraph g, int v, int dist[], int path[]){ //顶点默认从0到n int set[MAX], min, i, j, u;//对各个数组进行初始化for(i = 0; i < g.n; i++){dist[i] = g.edges[v][i];set[i] = 0;if(g.edges[v][i] < INF){path[i] = v;}else{path[i] = -1;}} set[v] = 1; path[v] = -1;//初始化结束，关键操作开始for(i = 0; i < g.n - 1; i++){min = INF;//找到的点   目前最小 //这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的for(j = 0; j < g.n; j++){if(set[j] == 0 && dist[j] < min){u = j;min = dist[j];}} set[u] = 1;//将选出的顶点并入最短路径中//这个循环以刚并入的顶点作为中间点，对所有通往剩余顶点的路径进行检测for(j = 0; j < g.n; j++) {//这个if判断顶点u的加入是否会出现通往顶点j的更短的路径，如果出现，则改变原来路径及其长度，否则什么都不做if(set[j] == 0 && dist[u] + g.edges[u][j] < dist[j]){dist[j] = dist[u] + g.edges[u][j];//更新路径长度 path[j] = u;//更新路径顶点 } } } 
}
int main() {init();int n, m;//n个点，m条边int a, x, y, w;cin >> m >> n;G.e = m;G.n = n;for(int i = 0; i < m; i++){cin >> x >> y >> w;insert(x, y, w);}Dijkstra(G, 0, dist, path);printfPath(path, 5);for(int i = 0; i < n; i++) {cout << dist[i] << " ";} return 0;
}
/*测试数据
12 7 
0 1 4
0 2 6
0 3 6
1 4 7
1 2 1
2 4 6
2 5 4
3 2 2
3 5 5
4 6 6
5 4 1
5 6 8
*/