动态规划:Warshall算法

2016年01月06日 原创
关键词: C++ 数据结构 算法 动态规划
摘要 Warshall算法是可以有效计算一个图的传递闭包的算法。

Warshall算法是一个很简洁也很好懂的算法。下面是它的算法核心:

rij(k) = rij(k-1) 或 rik(k-1)和rkj(k-1)

这个公式的意思可以这样理解:

判断一个点经过k步能否连通:

  1. 如果在k-1步的时候可以连通,则第k步也可以连通
  2. 如果在k-1步的时候,ik和kj是连通的,则第k步也可以连通

或许大家在这里会有疑问,为什么是ik和kj,而不是i0,0j或者i1,1j呢?

原因是k会在循环中不断递增,最后对于矩阵里所有的元素都进行过连通的测试。

下面是Warshall算法的伪代码。

算法   Warshall(A[1...n,1...n])

   //实现计算传递闭包的Warshall算法

   //输入:包括n个顶点有向图的邻接矩阵A

   //输出:该有向图的传递闭包

    R(0)←A

    for k←1 to n do

      for i←1 to n do

        for j←1 to n do

          R(k)[i,j]←Rk-1[i,j] or R(k-1)[i,k] and R(k-1)[k,j]

    return R(n)

 

该算法使用了三层循环,虽然十分简洁,但是时间复杂度仅仅属于Θ(n3)。

下面是Warshall的C++代码:

#include<iostream>
using namespace std;

void warshall(bool data[][4], int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++){
                data[i][j] = data[i][j] || data[i][k] && data[k][j];
            }
        }
    }
}

int main() {
    bool data[][4] = {
        { 0, 1, 0, 0 },
        { 0, 0, 0, 1 },
        { 0, 0, 0, 0 },
        { 1, 0, 1, 0 }
    };
    warshall(data,4);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cout << data[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

运行结果: