数据结构与算法学习笔记----Floyd算法

数据结构与算法学习笔记----Floyd算法

@@ author: 明月清了个风
@@ first publish time: 2024.12.20

Floyd算法

Floyd一种基于动态规划的最短路径算法，用于求出加权有向图中的任意两点之间的最短路径问题，并且适用于图中可能存在负权边的情况，但是要求不能有负权环，它能有效的求出图中所有节点之间的最短路径，适用稠密图。

基本思路

Floyd通过不断考虑每个节点作为中间节点，更新每对节点之间的最短距离

1. 初始化

   初始化dist[][]数组，对于任意两点之间之间距离初始化为无穷大，如有边存在，则初始化为边长。

2. 状态转移方程

   对于所有节点对$i$和$j$，使用每个中间节点$k$更新他们之间的最短路径

   $$dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\text{\hspace{1em}(1)}$$

   对应于一组$f(k,i,j)$来说，它表示的是经过$1\sim k$这些点，从$i$到$j$的最短距离，原始状态转移方程为

   $$dist[k,i,j]=dist[k-1,i,k]+dist[k-1,k,j]\text{\hspace{1em}(2)}$$

   式中：

   $dist[k,i,j]$表示经过$1\sim k$这些点，从$i$到$j$的最短距离；

   $dist[k-1,i,k]$表示经过$1\sim k-1$这些点，先从$i$到$k$的最短距离；

   $dist[k-1,k,j]$表示经过$1\sim k-1$这些点，从$k$到$j$的最短距离。

   最高位$k$可以省略，因此式(2)转化为式(1)。

注意点：

需要注意的是，floyd算法和bellman-ford算法同样可能会因为负权更新没有通路的两点之间的距离，因此最后的无法到达的判断也要大于一个大数，至于大数的选择就要看数据范围了，比如这道题中的最多会有$20000$条边，每条最长为$10000$，这意味这两者之间没有通路的两点本来应该无穷大的距离最多会减去$20000\times 10000$，也就是$10^8$数量级，所以这里不能像之前判断是否大于0x3f3f3f3f / 2，因为这个数是有可能取到的。

时间复杂度

Floyd算法的时间复杂度为$O(n^3)$，$n$表示节点数。

Acwing 854. Floyd求最短路

[原题链接](854. Floyd求最短路 - AcWing题库)

给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定$k$个询问，每个询问包含两个整数$x$和$y$，表示查询从点$x$到点$y$的最短距离，如果路径不存在，则输出impossible。

输入格式

第一行包含三个整数$n$,$m$,$k$。

接下来$m$行，每行包含三个整数$x$、$y$、$z$，表示存在一条从点$x$到点$y$的有向边，边长为$z$。

接下来$k$行，每行包含两个整数$x$，$y$，表示询问点$x$到点$y$的最短距离。

输出格式

共$k$行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出impossible.

数据范围

$1\le n\le 200$,

$1\le k\le n^2$,

$1\le m\le 20000$，

图中涉及边长绝对值均不超过$10000$.

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 210, inf = 1e9;

int dist[N][N];
int n, m, k;

void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    cin >> n >> m >> k;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
    
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
    }
    
    floyd();
    
    while(k --)
    {
        int x, y;
        cin >> x >> y;
        if(dist[x][y] > inf / 2) puts("impossible");
        else cout << dist[x][y] << endl;
    }
    
    return 0;
}