Dijkstra算法--单源最短路径算法

发表于 更新于

介绍

Dijkstra算法是典型的单源最短路径算法，用来计算某一点到其余各个点之间的最短距离，该算法主要试用于边距离为正数的请况。Dijkstra算法算是贪心思想实现的。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

题目

有一个图是有向带权图，里面有多个顶点，且有多条边。假设指定一个顶点为源点，那么源点到其他顶点的最短路径是多少呢，请为他找出来，如果没有这条路径，请用999999来表示达不到，顶点是自己的时候用0表示。

输入数据第一行是两个整数N、M（N<=100，M<=10000），N表示多少个顶点，M则表示有多少条边。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在顶点A与顶点B之间有一条路，权值为C。 源点默认为1

输出一行，表示源点到每个顶点的最短路径。

输入

5 12
1 2 1
1 4 3
1 5 2
2 3 5
2 4 3
2 5 8
3 2 4
3 5 1
4 3 7
4 5 12
5 1 3
5 4 10

输出

0 1 6 3 2

代码

因为是典型的dijkstra算法的应用，所以没有思考题目的思路，直接套用算法就可以了。但是在代码的实现的会注释。当然我下面的这个代码为了省一些事情，和题目不太一样，所以这就要你们自己思考修改了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>

using namespace std;

int length = 5;
//dis代表输出的列表，book代表记录顶点的列表
int dis[5], book[5];
//代表走不到的路，无限大
int inf = 9999999;
//源点，可以自己指定
int start;
//邻接矩阵
int map[5][5] = { {0, 1, inf, 3, 2}, { inf, 0, 5, 3, 8 },{ inf, 4, 0, inf, 1 },{ inf, inf, 7, 0, 12 },{ 3, inf, inf, 10, 0 } };

void init() {
	//设置初始预算值
	for (int i = 0; i < length; i++)
	{
		dis[i] = map[start][i];
		book[i] = 0;
	}

	//源点设置访问过
	book[start] = 1;
}

void dijkstra() {

	init();

	int min_flag;

	//循环找到最短路径
	for (int i = 0; i < length - 1; i++)
	{
		int min = inf;

		//找最近的顶点
		for (int j = 0; j < length; j++)
		{
			if (min > dis[j] && book[j] != 1)
			{
				book[j] = min;
				min_flag = j;
			}
		}

		book[min_flag] = 1;

		//设置最短路径
		for (int k = 0; k < length; k++)
		{
			if (dis[k] > dis[min_flag] + map[min_flag][k] && map[min_flag][k] < inf)
			{
				dis[k] = dis[min_flag] + map[min_flag][k];
			}
		}
	}

	//输出
	for (int i = 0; i < length; i++)
	{

		if (i == length -1)
		{
			cout << dis[i] << endl;
		}
		else
		{
			cout << dis[i] << " ";
		}
	}
}

void main() {
	start = 3;
	dijkstra();
}

解析dijkstra

首先我们要考虑的是如果要从一个源点找其他点的最短路径，我们就要考虑，如果1->2不是最短的，1->4->5->2也有可能比直接到要短。但是我们可以知道1一定是开始的点，2一定是结束的点，如果是最短的路，那么中间一定有一个1到其他顶点的直达路，或者是本身直达路就是最短的，如果无论如何中间都有一个直达路，那么就可以确定直达路最短的那个就是第一个找到的最短路径，然后我们通过这个点找到它的出边，因为第一个最短路作为中间点是最短的，这个时候它就只有两种情况了，要么本身直达路是最短的，要么使用第一个最短路径作为中间点。然后依次类推，就可以得出所有点的最短路径。

那么第一次循环的时候为什么只循环length-1次呢？因为我们初始了dis数组为0，且将源点设置为访问过，所以我们只需要找到其他点的最短路径就行了。

当然这是用的邻接矩阵的方法来写的，也有一种邻接表的方法，这个后面再写。