老程序员博客

编程生涯的最后一舞

当前位置：首页 > 技术 > 正文内容

Dijkstra 算法：求解非负权图的最短路径

访客 技术 2026年9月2日 2

Dijkstra 算法是一种用于查找图中两个顶点之间最短路径的算法。与 Bellman-Ford 算法相比，Dijkstra 算法的主要优势在于其效率，特别是在处理具有非负权重的边时。优化后的 Dijkstra 算法（通常使用优先队列）的时间复杂度通常优于 Bellman-Ford 算法（O(mn)），可以达到 O(m log n)。

Dijkstra 算法的核心思想是：每次从一个尚未确定最短路径的顶点集合中，选择一个距离起点最近的顶点。然后，基于这个选定的顶点，更新其所有相邻顶点的最短路径估计值。这个过程会一直持续，直到所有顶点都被访问过，此时起点到图中任意顶点的最短路径就已经确定。

为了高效地选择距离起点最近的未访问顶点，通常会使用一个最小堆（优先队列）来实现。堆中存储的是顶点及其到起点的当前最短距离估计值。

示例 1：Dijkstra 算法模板题

给定一个包含 n 个顶点和 m 条边的有向简单图，边的权重均为非负整数。需要处理 k 组查询，每组查询包含两个顶点 x 和 y，要求计算从 x 到 y 的最短路径长度。如果不存在路径，则输出 -1。

输入格式：

第一行包含三个整数 n, m, k，分别表示顶点数、边数和查询次数。

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

接下来 k 行，每行包含两个整数 x, y，表示一组查询。

输出格式：

输出共 k 行，每行一个整数，表示对应查询的最短路径长度。

样例输入：

3 3 2
1 2 3
2 3 2
3 2 1
1 3
3 1

样例输出：

5
-1

数据规模：

2 ≤ n ≤ 100000, 0 ≤ m ≤ 200000, 1 ≤ k ≤ 5, 1 ≤ x, y ≤ n, 1 ≤ z ≤ 10000

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> EdgeInfo; // {neighbor_node, weight}
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

vector<EdgeInfo> adj[MAXN]; // Adjacency list: adj[u] stores pairs {v, w} for edges u -> v with weight w
int shortestDist[MAXN];      // shortestDist[i] stores the shortest distance from source to node i

int n_nodes, m_edges, k_queries;

// Function to compute shortest paths from a given source node
void computeShortestPaths(int start_node) {
    // Initialize distances to infinity
    memset(shortestDist, 0x3f, sizeof(shortestDist));
    shortestDist[start_node] = 0;

    // Min-priority queue storing pairs {distance, node}
    priority_queue<EdgeInfo, vector<EdgeInfo>, greater<EdgeInfo>> pq;
    pq.push({0, start_node});

    while (!pq.empty()) {
        int current_dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // If we found a shorter path already, skip
        if (current_dist > shortestDist[u]) {
            continue;
        }

        // Relax edges outgoing from u
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (shortestDist[v] > shortestDist[u] + weight) {
                shortestDist[v] = shortestDist[u] + weight;
                pq.push({shortestDist[v], v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n_nodes >> m_edges >> k_queries;

    // Build the graph
    for (int i = 0; i < m_edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    // Process queries
    while (k_queries--) {
        int query_start, query_end;
        cin >> query_start >> query_end;
        computeShortestPaths(query_start);
        
        int result = shortestDist[query_end];
        if (result == INF) {
            cout << "-1" << endl;
        } else {
            cout << result << endl;
        }
    }

    return 0;
}

示例 2：寻找最佳居住点

在一个有 n 个顶点和 m 条边的无向图中，每条边的权重都为非负整数。需要找到一个顶点作为居住点，使得该点到指定的三个地点（商场、工作地点、医院）的距离之和最小。这三个地点由三个顶点 a, b, c 表示。

输入格式：

第一行包含两个整数 n, m，表示图的顶点数和边数。

接下来 m 行，每行包含三个整数 x, y, z，表示顶点 x 和 y 之间存在一条权重为 z 的边。

下一行包含三个整数 a, b, c，分别表示商场、工作地点和医院的顶点编号。

输出格式：

输出一个整数，表示到商场、工作地点和医院的最小距离之和。

样例输入：

4 3
1 2 1
2 3 1
3 4 1
1 2 4

样例输出：

3

数据规模：

3 ≤ n ≤ 5000, 0 ≤ m ≤ 10000, 1 ≤ x, y, a, b, c ≤ n, 1 ≤ z ≤ 10000。图连通，且 a, b, c 互不相同。

解题思路：

为了解决这个问题，我们可以分别以 a, b, c 作为起点，运行三次 Dijkstra 算法。这会生成三个距离数组：`dist_a` (从 a 到各点的最短距离)，`dist_b` (从 b 到各点的最短距离)，和 `dist_c` (从 c 到各点的最短距离)。然后，遍历图中的每一个顶点 i，计算 `dist_a[i] + dist_b[i] + dist_c[i]`，并找出这个和的最小值。

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> EdgeInfo; // {neighbor_node, weight}
const int MAXN = 5005;
const int MAXM_NODES = 10005; // Adjusted for max nodes, not edges
const int INF = 0x3f3f3f3f;

vector<EdgeInfo> adj[MAXN]; // Adjacency list
int dist_from_a[MAXN];
int dist_from_b[MAXN];
int dist_from_c[MAXN];
int current_dist[MAXN]; // Temporary storage for Dijkstra results

int mall_node, work_node, hospital_node;

// Dijkstra function, stores results in current_dist
void run_dijkstra(int start_node) {
    memset(current_dist, 0x3f, sizeof(current_dist));
    current_dist[start_node] = 0;

    priority_queue<EdgeInfo, vector<EdgeInfo>, greater<EdgeInfo>> pq;
    pq.push({0, start_node});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > current_dist[u]) {
            continue;
        }

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (current_dist[v] > current_dist[u] + weight) {
                current_dist[v] = current_dist[u] + weight;
                pq.push({current_dist[v], v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n_nodes, m_edges;
    cin >> n_nodes >> m_edges;

    // Build the undirected graph
    for (int i = 0; i < m_edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // Add edge in both directions for undirected graph
    }

    cin >> mall_node >> work_node >> hospital_node;

    // Run Dijkstra from mall
    run_dijkstra(mall_node);
    memcpy(dist_from_a, current_dist, sizeof(dist_from_a));

    // Run Dijkstra from work
    run_dijkstra(work_node);
    memcpy(dist_from_b, current_dist, sizeof(dist_from_b));

    // Run Dijkstra from hospital
    run_dijkstra(hospital_node);
    memcpy(dist_from_c, current_dist, sizeof(dist_from_c));

    int min_total_dist = INF;
    // Find the node that minimizes the sum of distances
    for (int i = 1; i <= n_nodes; ++i) {
        if (dist_from_a[i] != INF && dist_from_b[i] != INF && dist_from_c[i] != INF) {
            min_total_dist = min(min_total_dist, dist_from_a[i] + dist_from_b[i] + dist_from_c[i]);
        }
    }

    cout << min_total_dist << endl;

    return 0;
}

示例 3：有向图中的双向最短路径

在一个有 n 个顶点和 m 条边的有向图中，每条边的权重都为非负整数。需要找到一个顶点 k，使得从 k 出发，访问所有其他顶点并返回 k 的总时间（即从 k 到任意顶点 i 的最长路径，加上从任意顶点 i 返回 k 的最长路径）最小。

解题思路：

这个问题可以分解为两个子问题：

  1. 计算从源顶点 k 到图中任意顶点 i 的最短路径。
  2. 计算从任意顶点 i 到源顶点 k 的最短路径。

为了计算从任意顶点 i 到 k 的最短路径，我们可以反转所有边的方向，然后以 k 为起点运行 Dijkstra 算法。这样，在反向图上从 k 到 i 的最短路径，就等同于在原图上从 i 到 k 的最短路径。

设 `dist_to_k[i]` 表示从 k 到 i 的最短距离，`dist_from_k[i]` 表示从 i 到 k 的最短距离。

1. 运行 Dijkstra 算法，以 k 为源点，在原图上计算 `dist_to_k`。

2. 构建一个反向图，其中所有边的方向都被颠倒。然后，以 k 为源点，在反向图上运行 Dijkstra 算法，计算 `dist_from_k`。

最终，遍历图中的每一个顶点 i，计算 `dist_to_k[i] + dist_from_k[i]`。我们需要找到这个和的最大值。

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> EdgeInfo; // {neighbor_node, weight}
const int MAXN = 100005;
const long long INF = 0x3f3f3f3f3f3f3f3fLL; // Use long long for distances

vector<EdgeInfo> forward_adj[MAXN]; // Adjacency list for original graph
vector<EdgeInfo> backward_adj[MAXN]; // Adjacency list for reversed graph
long long dist_to_k[MAXN]; // Stores shortest distance FROM k TO i
long long dist_from_k[MAXN]; // Stores shortest distance FROM i TO k

int n_nodes, m_edges, k_source;

// Dijkstra function for forward graph
void compute_forward_shortest_paths(int start_node) {
    memset(dist_to_k, 0x3f, sizeof(dist_to_k));
    dist_to_k[start_node] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start_node});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist_to_k[u]) {
            continue;
        }

        for (const auto& edge : forward_adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist_to_k[v] > dist_to_k[u] + weight) {
                dist_to_k[v] = dist_to_k[u] + weight;
                pq.push({dist_to_k[v], v});
            }
        }
    }
}

// Dijkstra function for backward graph
void compute_backward_shortest_paths(int start_node) {
    memset(dist_from_k, 0x3f, sizeof(dist_from_k));
    dist_from_k[start_node] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start_node});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist_from_k[u]) {
            continue;
        }

        for (const auto& edge : backward_adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist_from_k[v] > dist_from_k[u] + weight) {
                dist_from_k[v] = dist_from_k[u] + weight;
                pq.push({dist_from_k[v], v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n_nodes >> m_edges >> k_source;

    // Build both forward and backward graphs
    for (int i = 0; i < m_edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        forward_adj[u].push_back({v, w});
        backward_adj[v].push_back({u, w}); // Reverse edge for backward graph
    }

    // Compute shortest paths from k
    compute_forward_shortest_paths(k_source);
    // Compute shortest paths to k (by running Dijkstra on reversed graph from k)
    compute_backward_shortest_paths(k_source);

    long long max_total_time = 0;
    // Find the maximum sum of distances
    for (int i = 1; i <= n_nodes; ++i) {
        // Check if both paths exist
        if (dist_to_k[i] != INF && dist_from_k[i] != INF) {
             max_total_time = max(max_total_time, dist_to_k[i] + dist_from_k[i]);
        }
    }

    cout << max_total_time << endl;

    return 0;
}
标签: Dijkstra
返回列表

上一篇：Go 语言方法机制与接收者规则解析

下一篇：clawdbot钩子机制深度解析：自定义AI助手行为

相关文章

Linux crontab 详解

1) crontab 是什么cron 是 Linux 的定时任务守护进程；crontab 是用来编辑/查看“按时间周期执行命令”的表（cron table）。常见两类：用户 crontab：每个用户一份（crontab -e 编辑）系统级 crontab / cron.d：可指定执行用户（/etc/crontab、/etc/cron.d/*）2) crontab 时间...

富文本里可以允许的 HTML 属性

一、所有标签默认允许的安全属性（极少）class        （可选）id           （通常建议禁用）title️ 注意：id 容易被滥用做锚点注入，很多系统直接禁用class 允许的话最好只允许固定前缀（如 editor-*）二、a 标签允许属性<a href="" t...

Mac 安装 Node.js 指南

方法一：通过官网安装包（最简单，适合初学者）如果你只是想快速安装并开始使用，这是最直接的方法。访问 Node.js 官网。页面会显示两个版本：LTS (Recommended For Most Users)：长期支持版，最稳定。建议选这个。Current：最新特性版，包含最新功能但可能不够稳定。下载 .pkg 安装包并运行。按照安装向导点击“下一步”即可完成。方法二：使用 Homebrew 安装（...

Dom\HTML_NO_DEFAULT_NS 的副作用：自动加闭合标签

在使用Dom\HTMLDocument时，Dom\HTML_NO_DEFAULT_NS 将禁止在解析过程中设置元素的命名空间, 此设置是为了与DOMDocument向后兼容而存在的。当使用它时，已知的一个副作用就是：自动加闭合标签例如 </img> 为什么会这样？当你使用：Dom\HTML_NO_DEFAULT_NS文档会变成 无命名空间模式，此时内部更接近 XML...

Laravel 事件和监听器创建

在 Laravel 中，使用 Artisan 命令创建 Events（事件） 和 Listeners（监听器） 是非常高效的。你可以通过以下几种方式来实现：1. 手动创建单个 Event如果你只想创建一个事件类，可以使用 make:event 命令：Bashphp artisan make:event UserRegistered执行后，文件将生成在 app/Even...

自定义域名解析神器 dnsmasq

什么是 dnsmasq？dnsmasq 是一个轻量级、功能强大的网络服务工具，专为小型和中等规模网络设计。它是一个综合的网络基础设施解决方案[1]。dnsmasq 能做什么？功能说明应用场景DNS 转发与缓存将 DNS 查询转发到上游服务器（ISP、Google DNS 等），并在本地缓存结果加快 DNS 查询速度，减少外部 DNS 流量本地 DNS解析本地网络设备的主机名，无需编辑&n...

发表评论

访客

◎欢迎参与讨论，请在这里发表您的看法和观点。

Copyright © agingcoder.cn

Powered By Z-BlogPHP. Theme by TOYEAN.