所有结点对最短路径问题(Floyd-Warshall算法)

所有结点对问题可以对所有结点都运行一次Dijkstra算法,若采用的是二插堆来实现最小优先队列,那么该算法的时间复杂度是O(VElgV). 但是Dijkstra算法写起来较复杂,这里讲的Floyd-Warshall算法是一种写法非常简单的最短路径算法,其时间复杂度是O(V^3),在非稀疏图的情况下,该算法的效率接近运行N次Dijkstra.(Floyd-Warshall算法适用于以邻接矩阵表示的图)

Floyd-Warshall算法的几个重要概念:
  1. 中间结点:设路径p = <v1,v2,v3…..v(n-1),vn>,那么v2到v(n-1)就叫做路径p的中间结点.
  2. 最短路径的结构:设结点编号为(1,2,3,4,….,n-1,n), 设D(i,j,k)表示是从vi到vj用了(1,2,3,4….,k-1,k)作为中间结点时的暂时的最短路径(k <= n),显然,当k取n时即D(i,j,n)就是从vi到vj的最短路径(以为当k=n时你考虑了从vi到vj的所有可能路径),因此很自然的运用动态规划,从k=1规划到k=n。// D(i,j,k)有几种特殊情况,D(i,i,k)=0. D(i,j,0) = w(i,j). w(i,j)就是连接vi和vj的弧的权重
所以现在的问题就是如何计算D(i,j,k). 要分两种情况考虑:
  1. 中间结点用到了k. 此时把该路径分成两段 p1(vi–>k) , p2(k–>vj)
    其中p1,p2所用到的中间结点必取自(1,2,3,…k-2,k-1),并且路径长度等于p1+p2
  2. 中间结点没有用到k. 那么该路径的中间结点必取自(1,2,3,…k-2,k-1)。

综上可以得到一个递归式: D(i,j,k)= min(D(i,j,k-1), D(i,k,k-1)+D(k,j,k-1)) C++实现源码:

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 1 << 29         //为测试数据随便定义个最大值2^29

void allPairs(int (*a)[5], int (*d)[5])  // 矩阵a存图, 矩阵d存最短路径。 简单起见我直接测试5*5的矩阵  
{
    for (int i = 0; i < 5; i++) //初始化d
        for (int j = 0; j < 5; j++)
            d[i][j] = a[i][j];

    for (int k = 0; k < 5; k++) 
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
int main()  
{
    int a[5][5] = {{0,3,8,MAX,-4}, {MAX,0,MAX,1,7}, {MAX,4,0,MAX,MAX},{2,MAX,-5,0,MAX},{MAX,MAX,MAX,6,0}};
    int b[5][5];
    allPairs(a, b);
    for (int i = 0; i < 5; i++){
        for (int j = 0; j < 5; j++)
            cout << b[i][j] << " ";
        cout << endl;
    }
    return 0;
}

参考书籍:
1. 算法导论第三版P406-408
2. Data Structures and Algorithm Analysis in C++ Third Edition P452-453