图多源最短路径问题(Floyd算法)

前言

求图多源最短路径问题有一种简洁优雅的算法–Floyd算法。

做法

1. 定义一个二维数组dist，dist[i][j]代表i到j的最短路径，如果i和j不可达，就初始化为无穷大，为了方便计算，我这里设为9999。
2. 定义一个二维数组next，next[i][j]代表i到j这条路径中i的下一个站点，如果i和j不可达，就初始化为-1。
3. 我们假设所有点经过k一定会到达另一个点，i到j如果可达，那么它有两条路径i->j和i->k—>j，我们通过比较这两条路径的大小来决定dist[i][j]的值，我们可以转化为一个动态方程来理解下：
dist[i][j] = Min{dist[i][j],dist[i][k]+dist[k][j]}
4. 同时我们还要记录next[i][j]的值，如果经过k的路径比较短，那么next[i][j] = next[i][k]

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

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

/**
 * 利用了动态规划
 * 时间复杂度为O(n^3)
 **/
void floyd(vector<vector<int>> &dist,vector<vector<int>> &next){
    size_t size = dist.size();
    for (int k = 0; k<size; k++) {
        for (int i = 0; i <size; i++) {
            for (int j = 0; j<size; j++) {
                if (dist[i][k]+dist[k][j]<dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
}


void printPath(int i,int j,vector<vector<int>> &next){
    if (next[i][j]==-1) {
        cout<<i<<" to "<<j<<" no path"<<endl;
        return;
    }
    cout<<i;
    while (i!=j) {
        i = next[i][j];
        cout<<"->"<<i;
    }
    cout<<endl;
}

int main(int argc, const char * argv[]) {
    vector<vector<int>> dist =
    {
        {0,9999,-2,9999},
        {4,0,3,9999},
        {9999,9999,0,2},
        {9999,-1,9999,0}

    };

    vector<vector<int>> next =
    {
        {-1,-1,2,-1},
        {0,-1,2,-1},
        {-1,-1,-1,3},
        {-1,1,-1,-1}
    };

    floyd(dist, next);

    for (int i = 0; i<dist.size(); i++) {
        for (int j = 0; j<dist.size(); j++) {
            cout<<dist[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

    for (int i = 0; i<dist.size(); i++) {
        for (int j = 0; j<dist.size(); j++) {
            printPath(i, j, next);
        }
        cout<<endl;
    }
    cout<<endl;

    return 0;
}

Comments