弗洛伊德算法（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为无法通行）