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

全栈程序员-站长 • 2022年5月18日下午6:40 • 未分类 • 阅读 32

大家好，又见面了，我是你们的朋友全栈君。

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

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

一：简介

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

(图来自于参考资料2)

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

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

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

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

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

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

看文字描述显得苍白无力，你可以结合上图，看下这个视频：http://v.youku.com/v_show/id_XMjQyOTY1NDQw.html
(dijkstra演示)，然后就清楚了。
我比较懒不想打字所以以上文字来源：
代码原创
http://www.cnblogs.com/wb-DarkHorse/archive/2013/03/12/2948467.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
*/

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/144803.html原文链接：https://javaforall.net