找出两点间的最短路径。

  • Dijkstra（不能搞负权图）
  • Bellman-Ford 和 SPFA（另一种写法）
  • Floyd

Dijkstra

时间复杂度：O(|V|*|V|)。如是用优先队列维护最小值，可 以做到O(|V|*log|E|)

Bellman-Ford

如果最短路存在，则最短路经过的边数不超过n-1 条，由此可有下面的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 0; i < n; i++) d[i] = INF;
d[0] = 0;
for(int k = 0; k < n-1; k++)
{
    //控制次数
    flag = false; //记录是否更新
    for(int i = 0; i < m; i++)
    {
        if(dis[v[i]] > dis[u[i]] + w[i])
        {
            dis[v[i]] = dis[u[i]] + w[i]; //松弛的过程
            flag = true;
        }
    }
    if (!flag) break;
}

再跑一遍，如果最短路还在更新，则有负权回路。

  • 最坏时间复杂度：O(|V|*|E|)。但一般没那么大。
  • 算法局限性：稠密图中复杂度远高于 Dijkstra

Floyd

Floyd算法利用了动态规划。用 d[i][j][k] 表示从 i 到 j，经过编号不超过 k 的点所得到的最短距离（郝东没讲清楚）。

状态转移方程：

1
d[i][j][k] = min{d[i][j][k-1],  d[i][k][k-1] + d[k][j][k-1];

再压缩一下就是标准的二维数组 Floyd 了。