一、弗洛伊德算法（Floyd）

Floyd算法的思想比较简单，它的核心代码只有5行；

1
2
3
4
5
for (int k = 0; k < G.vCount; ++k)
	for (int i = 0; i < G.vCount; ++i)
		for (int j = 0; j < G.vCount; ++j)
			if (G.arcs[i][j] > G.arcs[i][k] + G.arcs[k][j])
				G.arcs[i][j] = G.arcs[i][k] + G.arcs[k][j];

对于一个有向图G：

我们可以认为当前二维数组中的值表示的是两个顶点之间的直接路径长度（即中间不经过其它顶点进行中转时的路径）。这个直接路径并不一定是最短路径。
例如：G[1][3] = 6表示从1到3的直接路径长度为6，当我们引入2号顶点作为中转点时，（即先从顶点1走到顶点2，再从顶点2走到顶点3），从顶点1到3的路径长度可以更短，为G[1][2] + G[2][3] = 5;

上述思想的代码实现非常简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Floyd(Graph G)
{
	for (int k = 0; k < G.vCount; ++k) {
		for (int i = 0; i < G.vCount; ++i) {
			for (int j = 0; j < G.vCount; ++j) {
				if (G.arcs[i][j] > G.arcs[i][k] + G.arcs[k][j])
					G.arcs[i][j] = G.arcs[i][k] + G.arcs[k][j];
			}
		}
	}
	cout << "任意两点间的最短距离为：" << endl;
	//打印最终结果
	ShowGraph(G);
}

这段代码中，最外层的循环用来控制当前允许经过哪个点进行中转。内层的两个循环表示当经过此中转点时一个顶点到其他所有顶点的距离是否能更短，若能更短，则更新最短距离。用一句话概括就是：从i号顶点到j号顶点只经过前k号顶点的最短路径(比如当要经过k-1顶点进行中转时，图中的储存的路径已经是经过前k-1号顶点时的最短路径了)，这其实是一种“动态规划”的思想（可以根据 斐波那契数列 想象一下这个思想）。

由代码不难看出，Floyd算法的时间复杂度为O(n^3),因为要储存两两顶点间的最短路径，所以空间复杂度为O(n^2)（我在这里没有使用辅助空间，直接在原图中进行操作了）。

二、迪杰斯特拉算法（Dijkstra）

Dijkstra算法是一种“单源最短路径算法”（求一个顶点(源点)到其余各个顶点的最短路径），它是一种采用贪婪策略（在对问题求解时，总是做出在当前看来是最好的选择）实现的算法。

对于有向图G：

在算法中，我们声明一个dis数组用来储存源点到其余顶点的的最短路径的“预估值”。以0号顶点为源点，有：

在dis表中选择到源点“预估值”最小的顶点（不包括源点本身），为dis[1] = 2;选择1号顶点后，dis[1]的值就可以从“预估值”变成“确定值”了；为什么呢？因为目前到源点最近的顶点为1号顶点，且图中边的权重都是正数（此算法不适用于带负权图），因此，不可能找到一个中转点使得从源点到1号顶点的路径更短。
这样的话，我们就还需要使用一个数组book来标记源点到当前点的最短路径是否为确定值（一般使用两个列表来分别储存“预估值”与“确定值”）。

确定源点到1号顶点的最短路径之后，我们对1号顶点的所有出边进行松弛：对于1号顶点，有一条出边1->2，我们讨论当通过1号顶点进行中转时，源点到2号顶点的路径是否能更短，即比较dis[2]与dis[1] + G[1][2]的大小，如果更短，则更新dis[2]的值。这一过程称为边的松弛。
对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
void Dijkstra(Graph G, int origin)
{
	//dis：储存源点到其它点的最短距离，book：用来做标记，标记到当前点到源点的最短距离是否已被确定
	int *dis = new int[G.vCount], *book = new int[G.vCount];
	int i = 0, j = 0, k = 0, s = 0, min = MaxInt;
	for (i = 0; i < G.vCount; ++i) {
		//GetSub(G,origin)：获取源点在顶点表中的下标
		s = GetSub(G, origin);
		dis[i] = G.arcs[s][i];
	}
	//初始化标记
	for (i = 0; i < G.vCount; ++i) {
		book[i] = 0;
	}
	//设置源点到源点的最短距离为已确定
	book[s] = 1;
	//确定源点到dis表里的所有顶点的最短距离，算法核心
	for (i = 1; i < G.vCount; ++i) {
		min = MaxInt;
		//在未确定到源点最短距离的顶点中找到离源点最近的顶点
		for (j = 1; j < G.vCount; ++j) {
			if (book[j] == 0 && dis[j] < min) {
				min = dis[j];
				s = j;
			}
		}
		//设置s点到源点的最短距离为已知
		book[s] = 1;
		//对当前顶点的出边进行松弛
		for (k = 0; k < G.vCount; ++k) {
			//判断下标为s的顶点到下标为k的顶点间是否存在边，若存在，对其进行松弛操作
			if (G.arcs[s][k] < MaxInt) {
				if (dis[k] > dis[s] + G.arcs[s][k]) {
					dis[k] = dis[s] + G.arcs[s][k];
				}
			}
		}
	}
	//打印最短路径
	for (i = 0; i < G.vCount; ++i) {
		cout << "点" << origin << "到" << G.vexs[i] << "的最短距离为：" << dis[i] << endl;
	}

}

Dijkstra算法的时间复杂度为O(n^2)，在对算法的优化方面，可以使用最小堆在来实现查找最小“预估值”操作，若数据较多，且图为稀疏图时，通过邻接表来储存边，也能在一定程度上优化此算法的性能。

完整代码：

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
using namespace std;

const int Num = 50;
const int MaxInt = 32767;
struct Graph {
	int vexs[Num];			//顶点表
	int arcs[Num][Num];		//边表
	int vCount;				//顶点数量
	int aCount;				//边数量
};

//获取值在顶点表中下标
int GetSub(Graph G, int value)
{
	int i;
	for (i = 0; i < G.vCount; ++i) {
		if (G.vexs[i] == value)
			break;
	}
	return i;
}
//创建图（邻接矩阵）
void CreatMap(Graph &G)
{
	int t1, t2, w;
	//输入顶点信息
	for (int i = 0; i < G.vCount; ++i) {
		cin >> G.vexs[i];
	}
	for (int i = 0; i < G.vCount; ++i)
		for (int j = 0; j < G.vCount; ++j) {
			G.arcs[i][j] = MaxInt;
			if (i == j)
				G.arcs[i][j] = 0;
		}
			
	for (int i = 0; i < G.aCount; ++i) {
		cin >> t1 >> t2 >> w;
		int s1 = GetSub(G, t1);
		int s2 = GetSub(G, t2);
		if (s1 != G.vCount && s2 != G.vCount) {
			G.arcs[s1][s2] = w;
			//G.arcs[s2][s1] = w;			//无向图		
		}	
	}
}
//打印图
void ShowGraph(Graph G) 
{
	for (int i = 0; i < G.vCount; ++i) {
		for (int j = 0; j < G.vCount; ++j) {
			cout << G.arcs[i][j] << "\t";
		}
		cout << endl;
	}
}

//弗洛伊德算法
void Floyd(Graph G)
{
	for (int k = 0; k < G.vCount; ++k) {
		for (int i = 0; i < G.vCount; ++i) {
			for (int j = 0; j < G.vCount; ++j) {
				if (G.arcs[i][j] > G.arcs[i][k] + G.arcs[k][j])
					G.arcs[i][j] = G.arcs[i][k] + G.arcs[k][j];
			}
		}
	}
	cout << "任意两点间的最短距离为：" << endl;
	//打印最终结果
	ShowGraph(G);
}


/*
迪杰斯特拉算法
G：图
origin：源点（起点）
*/
void Dijkstra(Graph G, int origin)
{
	//dis：储存源点到其它点的最短距离，book：用来做标记，标记到当前点到源点的最短距离是否已被确定
	int *dis = new int[G.vCount], *book = new int[G.vCount];
	int i = 0, j = 0, k = 0, s = 0, min = MaxInt;
	for (i = 0; i < G.vCount; ++i) {
		//GetSub(G,origin)：获取源点在顶点表中的下标
		s = GetSub(G, origin);
		dis[i] = G.arcs[s][i];
	}
	//初始化标记
	for (i = 0; i < G.vCount; ++i) {
		book[i] = 0;
	}
	//设置源点到源点的最短距离为已确定
	book[s] = 1;

	//确定源点到dis表里的所有顶点的最短距离，算法核心
	for (i = 1; i < G.vCount; ++i) {
		min = MaxInt;
		//在未确定到源点最短距离的顶点中找到离源点最近的顶点
		for (j = 1; j < G.vCount; ++j) {
			if (book[j] == 0 && dis[j] < min) {
				min = dis[j];
				s = j;
			}
		}
		//设置s点到源点的最短距离为已知
		book[s] = 1;
		//对当前顶点的出边进行松弛
		for (k = 0; k < G.vCount; ++k) {
			//判断下标为s的顶点到下标为k的顶点间是否存在边，若存在，对其进行松弛操作
			if (G.arcs[s][k] < MaxInt) {
				if (dis[k] > dis[s] + G.arcs[s][k]) {
					dis[k] = dis[s] + G.arcs[s][k];
				}
			}
		}
	}

	//打印最短路径
	for (i = 0; i < G.vCount; ++i) {
		cout << "点" << origin << "到" << G.vexs[i] << "的最短距离为：" << dis[i] << endl;
	}

}

int main()
{
	Graph G;
	cin >> G.vCount >> G.aCount;
	CreatMap(G);
	ShowGraph(G);
	Floyd(G);
	Dijkstra(G, 0);
	system("pause");
	return 0;
}

/*
10 13
0 1 2 3 4 5 6 7  8 9
0 1 3
0 6 6
0 4 5
1 2 2 
1 9 9
2 3 1
3 6 3
4 5 3
5 6 2
6 7 2
6 9 3
7 8 6
8 9 8
*/

 上一页

.NET c#

 评论