数据结构：最短路径算法之Floyed算法

￡神魔★判官ぃ 2022-05-31 12:56 212阅读 0赞

# Floyed算法 #

Floyed-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 注意单独一条边的路径也不一定是最佳路径。

**时间复杂度O(n^3),只要有存下邻接矩阵的空间，时间一般没问题，并且不必担心负权边的问题。**

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    const int MAX = 1000000;
    // floyed算法可以计算得到任意的i到j的最短路径
    
    /*
    6 个节点
    1000000 1000000 10 100000 30 100
    1000000 1000000 5 1000000 1000000 1000000
    1000000 1000000 1000000 50 1000000 1000000
    1000000 1000000 1000000 1000000 1000000 10
    1000000 1000000 1000000 20 1000000 60
    1000000 1000000 1000000 1000000 1000000 1000000
    
    结果
    D[0]   D[1]   D[2]   D[3]   D[4]   D[5]
    0   1000000   10     50     30     60
    
    //节点0到节点5的最短路径是0 4 3 5
    */
    
    void floyd()
    {
        const int n = 6;
        int mat[6][6] =
        {
            1000000, 1000000, 10, 100000, 30, 100,
            1000000, 1000000, 5, 1000000, 1000000, 1000000,
            1000000, 1000000, 1000000, 50, 1000000, 1000000,
            1000000, 1000000, 1000000, 1000000, 1000000, 10,
            1000000, 1000000, 1000000, 20, 1000000, 60,
            1000000, 1000000, 1000000, 1000000, 1000000, 1000000 };
    
        int flag[6][6] = { 0 };
        //访问标志初始化
        for (int i = 0; i<n; i++)
            for (int j = 0; j<n; j++)
                flag[i][j] = -1;
    
        for (int k = 0; k<n; k++)
        {
            for (int i = 0; i<n; i++)
            {
                for (int j = 0; j<n; j++)
                {
                    if (mat[i][j] <= MAX && mat[i][k] + mat[k][j] < mat[i][j])
                    {
                        mat[i][j] = mat[i][k] + mat[k][j];
                        flag[i][j] = k;
                    }
                }
            }
        }
        for (int i = 0; i<n; i++)
            cout << mat[0][i] << "  ";
        cout << endl;
    
        //打印beg到end的最短路径节点信息
        int beg = 0, end = n - 1;
        int next = flag[beg][end];
        cout << beg << " -> ";
        while (next != -1)
        {
            cout << next << " -> ";
            next = flag[next][end];
        }
        cout << end << endl;
    
    }
    int main()
    {
        floyd();
        system("pause");
    }