Floyd-Warshall algorithm

2018/08/08 ALGO

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.

算法分析

Floyd-Warshall算法使用动态规划方案来解决带权图中每对顶点之间的最短路径问题。与Dijkstra算法相对的,Floyd-Warshall是解决全源最短路径问题。算法允许存在权值为负值的边,但是不允许存在权值是负的回路。Floyd-Warshall的算法复杂度是O(n^3)。

在算法导论中,解决单源最短路径问题的方案有Dijkstra以及Bellman-Ford。全源最短路径问题是单源的拓展,相当于执行n次单源最短路径算法。在求解最短路径问题中,最优子结构是两个节点之间的最短路径上包含路径其他节点的最短路径,下面是其数学描述:

给定带权图 G = (V, E),设 P = <v1, v2, ..., vk> 是从 v1 到 vk 的最短路径。
那么对于任意满足 1 <= i < j <= k 的 i 和 j ,有 <vi, ..., vj> 是节点 i 到节点 j 的最短路径。

Floyd-Warshall算法的原理是动态规划,假设 D(i,j,k) 表示从 i 到 j 的路径只经过 (1…k) 集合中的节点的最短路径的长度。有两种情况:

  1. 如果最短路径经过节点k,那么 D(i,j,k) = D(i,k,k-1) + D(k,j,k-1)
  2. 如果最短路径不经过节点k,那么 D(i,j,k) = D(i,j,k-1)

有状态转移方程:

D(i,j,k) = min(D(i,k,k-1) + D(k,j,k-1), D(i,j,k-1))

算法实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 图规模为小于100个节点
int e[100][100];
// 无穷远
int inf = 99999999;

int main(){
    // n个节点,m条边
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j){
                e[i][j] = 0;
            } else {
                e[i][j] = inf;
            }
        }
    }
    // 读入有向边
    for(int i=1;i<=m;i++){
        scanf("%d %d %d", &t1, &t2, &t3);
        e[t1][t2] = t3;
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(e[i][j] > e[i][k] + e[k][j]){
                    e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }
    return 0;
}

问题延展

在上述问题的基础上,每个节点带有点权,定义最短路径为节点 i 到节点 j 加上路径中的节点最大的点权,如何求最短路径呢?

注意到在Floyd-Warshall算法的三层循环中,最外层循环的k表示路径的中转点,是从节点1到节点n依次遍历的。在这个问题里,我们先对给定的节点的点权从小到大排序,k表示从新节点1到新节点n遍历。这样每次循环添加到最短路中的中转点的点权是以此增大的。最短路中的中转点变多,最短路会越短,但是由于添加的点权也在变大,所以需要新的松弛操作:

dist[i][j] = min(dist[i][j], e[i][j] + max(max(p[i], p[j]), p[k]))

其中dist是节点 i 到 j 的带点权的最短路径,e是节点 i 到 j 的不带点权的最短路径,p是节点的点权。

Search

    Table of Contents