图论中一个经典问题就是求最短路。最为基础和最为经典的算法莫过于 Dijkstra 和 Floyd 算法，一个是贪心算法，一个是动态规划。这也是算法中的两大经典代表。用一个简单图在纸上一步一步演算，也是非常好理解的。理解透自己多默写几次就可以记住，机试时基本的工作往往就是高速构造邻接矩阵了。
对于平时的练习，一个非常厉害的 ACMer @BenLin_BLY 说：“刷水题能够加快我们编程的速度，做经典则能够让我们触类旁通，初期假设遇见非常多编不出。最好还是就写伪代码，理思路。在纸上进行总体分析和一步步的演算，然后在转换成代码。再重复迭代”。Linus 不是也说了 "Nobody actually creates perfect code the first time
around, except me. But there’s only one of me." ^_^ 对于算法的学习，绝大多数都是把问题分解变形，然后套用曾经或别人的思路。
仅仅有把经典的算法都烂熟于心时，解决这个问题时才干够做到不知不觉的套用已有的思路和经验。能让我们走的更远的仅仅有热情和方法！
当认准一件事有价值时，我们要做的就是长期坚持，既然熟练掌握经典算法这么有价值。那么接下来要做的就是重复训练直到烂熟于心 ^_^
单源最短路
给定起点 start, 求到随意点的最短路 Dijkstra 算法，前提不能有负权边和孤立点：
- 贪心算法：每次找近期的点，局部最优等于全局最优，数学归纳法可证
- 维护起点 start 到每一个点的距离
- 时间复杂度 O(n^2)
- 附加空间复杂度 O(n)
Dijkstra 算法伪代码：
Q = {} // 已求出到 start 点最短路的点集合，初始为空
d[s] = 0, 其余值为正无穷大
while (|Q| < |V|) // 数学符号|A|表示集合A的点数
取出不在Q中的最小的d[i]
for (i相邻的点j，j不属于Q)
d[j] = min(d[j], d[i] + c[i][j]) //维护距离
Q = Q + {i}
全局最短路
求出图中随意两点最短路，利用 Floyd 算法，对负权边仍然有效：
- 动态规划：每次增加一个点
- 维护随意两点间的距离
- 时间复杂度 O（n^3）
- 附加空间复杂度 O（n^2）
Floyd 算法伪代码: # 直接改成 Python 了。没办法就是喜欢 Python :)
for k in range(0, n):
for i in range(0, n):
for j in range(0, n):
g[i][j] = min(g[i][j], g[i][k]+g[k][j])
小实验
一个图例如以下所看到的：
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdGhpc2lubm9jZW5jZQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">
源码 ( C 实现）
#include <stdio.h>
#define N 65536 /* 计算有 9 个点的图的单源最短路 */
void Dijkstra(int graph[9][9], int start, int path[9]){
int num=9, min, vertex, i, j;
int flag[num];
for(i = 0; i < num; ++i){ //初始化全部点都未计算，第一次距离直接读邻接矩阵
path[i] = graph[start][i];
flag[i] = 0;
} for(i = 0; i < num; ++i){
min = N;
for(j = 0; j < num; ++j){
if(flag[j] == 0 && min > path[j]){ //求未计算过的点中距离 start 近期点
min = path[j];
vertex = j;
}
}
flag[vertex] = 1; //将上面计算的点标记为计算过
for(j = 0; j < num; ++j){ //维护全部未计算过点的距离
if(flag[j] == 0 && path[j] > path[vertex] + graph[vertex][j]){
path[j] = path[vertex] + graph[vertex][j];
}
}
}
} /* 计算一个 9 个点的图全部点到全部点间的最短路 */
void Floyd(int graph[9][9]){
int num = 9, i, j, k;
for(k = 0; k < num; ++k){ //中转点
for(i = 0; i < num; ++i){ //出发点
for(j = 0; j < num; ++j){ //到达点
if(graph[i][j] > graph[i][k] + graph[k][j]){
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
} int main() {
int graph[9][9]={
{0, 1, 5, N, N, N, N, N, N},
{1, 0, 3, 7, 5, N, N, N, N},
{5, 3, 0, N, 1, 7, N, N, N},
{N, 7, N, 0, 2, N, 3, N, N},
{N, 5, 1, 2, 0, 3, 6, 9, N},
{N, N, 7, N, 3, 0, N, 5, N},
{N, N, N, 3, 6, N, 0, 2, 7},
{N, N, N, N, 9, 5, 2, 0, 4},
{N, N, N, N, N, N, 7, 4, 0}
};
int start=0, path[9], i, j;
Dijkstra(graph, start, path); //计算结果写入 path 数组
printf("点 %d 到全部点的最短距离：\n", start);
for(i=0; i<9; ++i){
printf("%d ",path[i]);
} Floyd(graph); //计算后的结果也直接写入graph
printf("\n全部点到全部点的最短距离\n");
for(i=0; i<9; ++i){
for(j=0; j<9; ++j){
printf("%d ",graph[i][j]);
}
printf("\n");
} return 0;
} /****** 执行结果 ***********
点 0 到全部点的最短距离：
0 1 4 7 5 8 10 12 16
全部点到全部点的最短距离
0 1 4 7 5 8 10 12 16
1 0 3 6 4 7 9 11 15
4 3 0 3 1 4 6 8 12
7 6 3 0 2 5 3 5 9
5 4 1 2 0 3 5 7 11
8 7 4 5 3 0 7 5 9
10 9 6 3 5 7 0 2 6
12 11 8 5 7 5 2 0 4
16 15 12 9 11 9 6 4 0
*****************************/