Ⅰ. 推荐课程
【浙江大学】数据结构，浙大的数据结构讲的很精炼，不枯燥易懂，十分适合数据结构的学习。
以下笔记也是根据以该课程为主，并加以具体实现代码。
Ⅱ. Floyd算法
Dijkstra算法可以求解单个点到其他点的最短路径，若要求任意两点之间的最短距离，使用Dijkstra算法则显得有些麻烦。为了解决这个问题，我们可以使用Floyd算法。
Floyd算法：Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。其时间复杂度为$O(N^3)$（因为代码里面有三个for循环），空间复杂度为$O(N^2)$。
Floyd算法采用了动态规划的思想，当求任意两点i，j的最短路径时有两种可能：
- i直接到j，即Dis(i, j)
- i经过某个点v到j，即Dis(i,v) + Dis(v,j)
通过将上述两种情况相比较，从而确定i，j两点之间的最短路径。假设图G一共有N个顶点，分别用这N个顶点作为中介点进行路径更新，更新N此后即可求得任意两点之间的最短路径。
Ⅲ. 代码
在编写代码的时候，我们需要两个N*N的数组dist和path，分别表示i，j两点之间的最短距离，以及i，j两点最短距离所经过的顶点。
关于三个for循环顺序为k，i，j的解释。
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
// 邻接矩阵
typedef struct _graph{
char vexs[MAX]; // 顶点集合
int vexnum; // 顶点数
int edgnum; // 边数
int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;
/*
* floyd最短路径。
* 即，统计图中各个顶点间的最短路径。
*
* 参数说明：
* G -- 图
* path -- 路径。path[i][j]=k表示，"顶点i"到"顶点j"的最短路径会经过顶点k。
* dist -- 长度数组。即，dist[i][j]=sum表示，"顶点i"到"顶点j"的最短路径的长度是sum。
*/
void floyd(Graph G, int path[][MAX], int dist[][MAX]){
// 初始化
for (int i = 0; i < G.vexnum; i++){
for (int j = 0; j < G.vexnum; j++){
dist[i][j] = G.matrix[i][j]; // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
path[i][j] = -; // "顶点i"到"顶点j"的最短路径是经过顶点j。
}
}
// 计算最短路径，k表示中介点
for (int k = 0; k < G.vexnum; k++){
for (int i = 0; i < G.vexnum; i++){
for (int j = 0; j < G.vexnum; j++){
// 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
int tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
if (dist[i][j] > tmp){
// "i到j最短路径"对应的值设，为更小的一个(即经过k)
dist[i][j] = tmp;
// "i到j最短路径"对应的路径，经过k
path[i][j] = k;
}
}
}
}
// 打印floyd最短路径的结果
printf("floyd: \n");
for (int i = 0; i < G.vexnum; i++){
for (int j = 0; j < G.vexnum; j++)
printf("%2d ", dist[i][j]);
printf("\n");
}
}
