Floyd_Warshall(任意两点之间的最短路)

O(V^3)

案例：

1 2 2

1 3 5

2 3 1

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

const int MAX_V = 100;
int d[MAX_V][MAX_V];//d[u][v] 表示边e=(u,v)的权值（不存在时设为INF，不过d[i][i] = 0）
int V;//顶点数

void warshall_floyd()
{
    for(int k = 0; k < V; k++)
    {
        for(int i = 0; i < V; i++)
        {
            for(int j = 0; j < V; j++)
            {
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
            }
        }
    }
}
int main()
{
    return 0;
}

巴特西

Floyd_Warshall(任意两点之间的最短路)

最新文章

热门文章