图的最短路径算法

|| 算法名称 || 时间复杂度 || 空间复杂度 || || dijkstra+heap || O(elog(e+n)) || O(n) || || bellman-ford || O(ne) || O(n) || || spfa || O(ke) || O(n) || || floyd-warshall || O(n^3) || O(n^2) ||

多源最短路径

Floyd算法

时间复杂度：O(V^3)

基本思想：三重循环遍历所有的顶点，若i，j两个点间，有一个点k，经过路径i->k->j要小于i->j则更新i->j的距离。三重循环结束，即可得到两两点间的距离最值。需要注意的是，i，j，k必须各不相同。

参考：http://hihocoder.com/problemset/problem/1089

伪代码：

for k = 1 .. N
    for i = 1 .. N 
        for j = 1 .. N
            若i, j, k各不相同
                MinDistance[i, j] = min{MinDistance[i, j], MinDistance[i, k] + MinDistance[k, j]}

单源最短路径--SSSP

Dijkstra

时间复杂度：O(VV+E) -> O（ElogV）

简单理解：以顶点为单位，开始时，源点d[0] = 0，其他d[x] = +∞。设置一个set，存放已经计算好的顶点。开始时候，只有源点在set中。每次选取一个与set邻接的顶点vx，并且vx距离v0最近，加入到set中，并更新vx邻接的顶点vy的d为d[vy] = min(d[vy], d[vx] + dis(x, y))。邻接的顶点vx的选取可以用heap来优化，使得复杂度下降到O（E*logV）

不足：边的权值不能为负数

Bellman-Ford

时间复杂度：O(VE)

简单理解：核心，松弛计算，relax() 数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；

以下操作循环执行至多n-1次，n为顶点数：

对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

SPFA (Shortest Path Faster Algorithm)

参考：http://hihocoder.com/problemset/problem/1093

Jimmy Blog