最短距离查询算法：C++ 代码实现及详解

题目描述

给定一个包含 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 <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<vector<pair<int, int>>> graph;

// 使用 Dijkstra 算法计算单源最短路径
vector<int> dijkstra(int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d > dist[u]) {
            continue; // 如果当前路径不是最短路径，则跳过
        }
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    graph.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({y, z});
    }
    for (int i = 0; i < k; ++i) {
        int a, b;
        cin >> a >> b;
        vector<int> dist = dijkstra(a);
        if (dist[b] == INF) {
            cout << "impossible" << endl;
        } else {
            cout << dist[b] << endl;
        }
    }
    return 0;
}

算法原理

本代码使用了 Dijkstra 算法来计算单源最短路径。Dijkstra 算法是一种贪心算法，它从起点开始，逐步扩展最短路径，直到到达终点。算法的步骤如下：

初始化所有节点的距离为无穷大，起点距离为 0。
将起点加入优先队列，优先队列按照距离从小到大排序。
从优先队列中取出距离最小的节点 u。
遍历与节点 u 相连的所有节点 v，如果节点 u 到节点 v 的路径比当前节点 v 的距离更短，则更新节点 v 的距离。
将更新后的节点 v 加入优先队列。
重复步骤 3-5，直到优先队列为空。

代码解释

graph 数组用于存储图的邻接表表示，每个元素是一个 vector<pair<int, int>>，表示该节点的邻接节点和对应的边权重。
dijkstra(int start) 函数用于计算从起点 start 到所有节点的最短距离，返回一个 vector<int>，表示每个节点的距离。
dist 数组用于存储每个节点到起点的距离，初始化为 INF。
pq 是一个优先队列，用于存储待扩展的节点，优先队列按照距离从小到大排序。
main() 函数用于读取输入并调用 dijkstra() 函数计算最短路径距离。

总结

本文章详细讲解了图论中的最短距离查询问题，并提供了完整的 C++ 代码实现。文章涵盖了问题的描述、输入输出格式、样例分析、算法原理以及代码解释，适合学习数据结构与算法的读者。希望这篇文章能够帮助您更好地理解和解决最短距离查询问题。