动态规划:Floyd算法

2016年01月06日 原创
关键词: C++ 数据结构 算法 动态规划
摘要 Floyd算法可以计算一个加权连通图的完全最短路径。

Floyd算法和Warshall算法非常相似。它是用来解决完全最短路径问题的算法。只要图中不包含长度为负的回路,这个算法既可以应用于无向加权图也可以应用于有向加权图。明白了Warshall算法之后,对于Floyd算法就能明白90%了。

动态规划:Warshall算法

在明白了Warshall算法之后,Floyd算法只需要把Warshall算法的核心换成Floyd算法的核心就可以了。

下面是Floyd算法的核心:

dij(k)=min{dij(k-1),dik(k-1)+dkj(k-1)}

以下是Floyd算法的伪代码:

算法   Floyd(W[1...n,1...n])

   //实现计算完全最短路径的Floyd算法

   //输入:图的权重矩阵W

   //输出:包含最短路径长度的距离矩阵

   D←W

   for k←1 to n do

     for i←1 to n do

       for j←1 to n do

         D[i,j]←min{D[i,j],D[i,k]+D[k,j]}

   return D

Floyd算法的效率和Warshall算法是一样的,都是属于Θ(n3)。

下面是Floyd算法的C++代码:

#include<iostream>
#include<algorithm>
#define inf 999999
using namespace std;
void floyd(int 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] = min(data[i][j], data[i][k] + data[k][j]);
            }
        }
    }
}
int main() {
    int data[][4] = {
        { 0, inf, 3, inf },
        { 2, 0, inf, inf },
        { inf, 7, 0, 1 },
        { 6, inf, inf, 0 }
    };
    floyd(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;
}

运行结果: