dijkstra算法

缘起

dijkstra算法是非负权有向网到单源的最短路径的算法.

dijkstra算法的证明:

如果在某一轮中一个顶点i是d[i] 最短的那个（从而i需要加入U，而引入i的掮客是j）. 那么d[i]就是单源0到i的最短路径了. 反证法. 如果存在别的路径0–>x–>i更小的话, 则考虑x有没有加入U呢? 如果已经在U中了, 那么为什么i没有在x选择的时候就加入呢? 如果尚没有在U中, 0–>x比d[i]还大, 又怎么可能0–>x–>i短于d[i]呢? （除非x–>i是负权边，所以dijkstra不允许有负权边）

分析

下面代码中U和V的具体含义参见 【1】

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include "stdafx.h"
#include <iostream>
#include <queue>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;
const int MAX_NUM = 20;
const int INF = 0x3f3f3f3f;


struct Graph
{
	int n; // 顶点的实际个数
	int adj[MAX_NUM][MAX_NUM]; // 邻接矩阵表示法
	int distance[MAX_NUM]; // 各个顶点到单源1号顶点（注意，本程序是写死了单源的,就是1号顶点）的最短距离
	bool isIn[MAX_NUM];// 是否已经引入了U
	int neighbor[MAX_NUM]; // neighbor[i] = j 表示是j将i拉入U中去的. 这个数组的作用是确定最后最短路径怎么构成的

	Graph()
	{
		memset(adj, 0x3f, sizeof(adj)); // 全部最大
		memset(isIn, 0,sizeof(isIn));
		isIn[1] = true; // 1这个顶点在MST中
		distance[1] = 0; // 单源到自己的最短长度显然是0
		puts("输入顶点的个数");
		scanf("%d", &n);
		puts("输入各边起点、终点及其权重");
		int x,y,w;
		while(~scanf("%d%d%d", &x, &y, &w)) adj[x][y] = w;
		for (int i = 2; i<=n; i++)
		{
			distance[i] = adj[1][i]; // 初始化各个顶点到单源1的距离
			neighbor[i] = 1; // 伊始都是1将其引入
		}
	}

	void dijkstra() // dijkstra算法用到了2个选择排序, 是堆优化的契机，但是懒得写代码了
	{
		int m = n-1;
		while(m--) // 每次拉进一个点入MST
		{
			int _min = 0; // 选择拉谁入MST
			int mindistance = INF;
			for (int i = 2; i<=n;i++) if (!isIn[i] && mindistance>distance[i]) mindistance = distance[_min = i];
			isIn[_min] = true; // _min 加入U
			for (int i = 2; i<=n;i++)  // 最后发现还是要把 _min 拉入U , 然后来更新distance, 以及决定neighbor
			{
				if (!isIn[i] && distance[i] > mindistance+adj[_min][i]) // 这部分是prim和dijkstra唯一的不同点
				{
					distance[i] = mindistance+adj[_min][i]; // 松弛
					neighbor[i] = _min;  // 更新neighbor
				}
			}
		}
		for (int i = 1; i<=n; i++)
		{
			printf("1到%d的最短路径是%d: ", i, distance[i]);
			printPath(i);
			puts("");
		}
	}

private:

	void printPath(int i) // 打印路径
	{
		if (i == 1)
		{
			printf("%d", i);
			return;
		}
		printPath(neighbor[i]);
		printf(" -> %d", i);
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.dijkstra();
	return 0;
}
/*
测试数据
6
1 2 1
1 3 12
2 3 9
2 4 3
4 3 4
3 5 5
4 5 13
4 6 15
5 6 4
*/

观照上述算法，我们知道dijkstra和prim是极为相似的（【1】）. dijkstra算法的正确性是由其弧的权的非负性决定的. 这是显然的，如果你的权是负数, 则我可以一圈一圈又一圈的绕，每绕一圈就能减少路径. 则就没有最短路径.

更确切的说:

Dijkstra算法的正确性是由弧(或者边)的权的非负性决定的. 举个最直观的例子,求的是各个顶点到单源0号顶点的最短距离,第一个被发现到0号（之所以是到0号顶点是因为此时U中只有一个单源0号顶点）最短的是1号顶点,然后将1号顶点加入U中（并且1号顶点到0号顶点的最短路径已经固定下来了）,第二轮发现的到U最短的是2号顶点，但是如果1到2的边或者弧是非负权的则不可能1到0的最短路径能够缩短，因为如果要缩短的话，只能是0到2+2到1的长度<0到1的长度，但是0到1的长度<=0到2的长度,所以不可能，但是如果2到1的弧或者边是负权的，则能更新0到1的最短路.比方2到1是-3,0到2是4,0到1是2，则从0到2再到1就比直接从0到1快，尽管1是第一轮发现的到0最短的顶点。

dijkstra算法的复杂度显然是 O(n^2), 经过堆优化 可以到达 O(nlogn)

参考

【1】https://yfsyfs.github.io/2019/05/25/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E4%B9%8BPrim%E7%AE%97%E6%B3%95/