弗洛伊德算法（Floyd）求最短路徑

弗洛伊德算法

圖來源于百度百科：Floyd算法

其時間複雜度為：O(n^3)，（這時間複雜度，分分鐘TLE。。。。。）

//#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<math.h>
#include<stack>
using namespace std ;
typedef long long ll;
#define MAXN 10005
#define INF 0x3f3f3f3f
#define MALL (BiTnode *)malloc(sizeof(BiTnode));

int path[MAXN][MAXN];       //最短路徑上頂點vj的前一項的序号
int D[MAXN][MAXN];          //vi到vj的最短路徑

void init(int n)
{
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
        if(i == j)
            D[i][j] = 0;
         else 
            D[i][j] = INF;
}

void PATH(int n)
{
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            if(D[i][j] < INF && i!=j)
                path[i][j] = i;
            else
                path[i][j] = -1;
}

void floyd(int n)							//floyd算法
{
    for(int k=0; k<n; ++k)
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                if(D[i][k] + D[k][j] < D[i][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                    path[i][j] = path[k][j];			//更新j的前驅為k
                }
}

int main()
{
    cout << "請輸入頂點的個數和邊的關系數" << '\n';
    int n, m;               //n個頂點和m條邊關系
    cin >> n >> m;
    init(n);
    cout << "\n請依次輸入各組邊的關系" << '\n';
    for(int i=0; i<m; ++i)
    {
        int u, v, len;
        cin >> u >> v >> len;
        D[u][v] = len;
    }
    PATH(n);
    floyd(n);
    cout << "\n用弗洛伊德算法計算後整個矩陣的最短路徑為：" << '\n';
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            if(D[i][j] < INF)
            cout << D[i][j] << ' ';
            else
                cout << -1 << ' ';
        }
        cout << '\n';
    }
}

           

樣例測試：

6 8

0 2 10

0 4 30

0 5 100

1 2 5

2 3 50

3 5 10

4 3 20

4 5 60

樣例輸出：（注意：-1為無法通行）