最短距离查询算法：Floyd 算法实现

题目描述

给定一个 n 个顶点 m 个边的有向图，图中不存在重边和自环，边的权重都是整数。再给定 k 次查询，每次查询包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短路径的距离。如果路径不存在，则输出 'impossible'，如果存在，则输出最短路径的距离。

输入格式

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

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

接下来 k 行，每行对应依次询问，包含两个整数 a, b，表示询问从顶点 a 到顶点 b 的最短路径距离。

输出格式

共 k 行，每行输出一个整数，表示这次询问的结果，如果两点间存在最短路径，则输出最短路径的距离，如果不存在，则输出 'impossible'。

样例 #1

样例输入 #1

样例输出 #1

impossible
impossible
impossible
impossible
impossible
impossible
8
impossible

提示

$$1 \le n \le 200$$ $$1 \le k \le n^2$$ $$1 \le m \le 20000$$ 图中的每条边的权重值不大于 50。

代码实现

C++ 代码

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

const int N = 210, M = 2010;

struct Node
{
    int a, b, w;
}node[M];

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

void floyd()
{
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
    for (int i = 0; i < m; i ++ )
    {
        auto t = node[i];
        dist[t.a][t.b] = min(dist[t.a][t.b], t.w);
    }
    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 = 0; i < m; i ++ ) cin >> node[i].a >> node[i].b >> node[i].w;

    floyd();

    while (k -- )
    {
        int a, b;
        cin >> a >> b;
        if (dist[a][b] > 0x3f3f3f3f / 2) puts("impossible");
        else cout << dist[a][b] << endl;
    }
    return 0;
}

Python3 代码

N = 210
M = 2010

# 初始化节点信息和距离矩阵
node = [0] * M
dist = [[float('inf')] * N for _ in range(N)]

# 输入图信息
n, m, k = map(int, input().split())
for i in range(m):
    a, b, w = map(int, input().split())
    node[i] = (a, b, w)
    dist[a][b] = min(dist[a][b], w)

# Floyd 算法
def floyd():
    for i in range(1, n + 1):
        dist[i][i] = 0
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

floyd()

# 输入查询信息并输出结果
for _ in range(k):
    a, b = map(int, input().split())
    if dist[a][b] == float('inf'):
        print("impossible")
    else:
        print(dist[a][b])

代码解释

C++ 代码解释

结构体定义: 使用 Node 结构体存储每条边的信息，包括起点 a，终点 b 和权重 w。
距离矩阵: 使用二维数组 dist 存储任意两点之间的最短距离。
Floyd 算法: floyd() 函数实现 Floyd 算法，计算任意两点之间的最短距离。
- 首先将 dist 矩阵初始化为无穷大，并设置对角线元素为 0。
- 遍历所有边，将起点和终点之间的距离设置为边的权重。
- 使用三层循环，枚举中间点 k，起点 i 和终点 j，更新 dist[i][j] 的值，即 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
查询处理: 使用循环处理 k 次查询，读取起点 a 和终点 b，并根据 dist[a][b] 的值判断路径是否存在，输出相应的结果。

Python3 代码解释

初始化: 使用列表存储节点信息和距离矩阵。
输入: 使用 input() 函数读取图信息和查询信息。
Floyd 算法: 使用嵌套循环实现 Floyd 算法，计算所有点对之间的最短距离。
查询处理: 使用循环处理 k 次查询，读取起点 a 和终点 b，并根据 dist[a][b] 的值判断路径是否存在，输出相应的结果。

总结

本文介绍了使用 Floyd 算法解决有向图的最短距离查询问题的详细步骤和代码实现。Floyd 算法是一种简单易懂且通用的算法，适用于解决任意两点之间的最短距离问题。

在实际应用中，需要根据具体的需求选择合适的算法，例如对于稀疏图，Dijkstra 算法或 Bellman-Ford 算法可能比 Floyd 算法更加高效。

希望本文能帮助你更好地理解和应用 Floyd 算法。