图的最短路径算法：Dijkstra算法详解

创作时间:

作者:

@小白创作中心

图的最短路径算法：Dijkstra算法详解

引用

CSDN

https://blog.csdn.net/2302_77582029/article/details/146291449

图的最短路径问题是图论中的经典问题，Dijkstra算法是解决这一问题的常用方法。它适用于带权有向图或无向图，且权重为非负数。本文将详细介绍Dijkstra算法的原理、实现方法、优化技巧以及典型应用场景，帮助读者全面掌握这一重要算法。

1. Dijkstra算法的原理

1.1 基本思想

Dijkstra算法通过贪心策略逐步扩展最短路径树，每次选择当前距离起点最近的节点，并更新其邻居节点的距离。

1.2 算法步骤

初始化距离数组，起点的距离为0，其他节点的距离为无穷大。
选择距离起点最近的未访问节点，更新其邻居节点的距离。
重复步骤2，直到所有节点都被访问。

1.3 示例

以下是一个带权图的示例：

节点: 0 --(4)--> 1 --(1)--> 2
 |             /          |
(2)         (5)         (3)
 |         /              |
 3 --(1)--> 4 --(2)--> 5

从节点0出发，Dijkstra算法的执行过程如下：

初始距离：
[0, ∞, ∞, ∞, ∞, ∞]
访问节点0，更新邻居节点1和3的距离：
[0, 4, ∞, 2, ∞, ∞]
访问节点3，更新邻居节点4的距离：
[0, 4, ∞, 2, 3, ∞]
访问节点4，更新邻居节点5的距离：
[0, 4, ∞, 2, 3, 5]
访问节点1，更新邻居节点2的距离：
[0, 4, 5, 2, 3, 5]
访问节点2，无更新。
访问节点5，无更新。

最终最短路径距离：
[0, 4, 5, 2, 3, 5]

2. Dijkstra算法的实现

以下是Dijkstra算法的C++实现代码，使用优先队列优化。

2.1 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

void dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX); // 距离数组
    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;
        pq.pop();
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    cout << "从起点 " << start << " 到各节点的最短距离:" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "节点 " << i << ": " << dist[i] << endl;
    }
}

int main() {
    int n = 6;
    vector<vector<pair<int, int>>> graph(n);
    graph[0].push_back({1, 4});
    graph[0].push_back({3, 2});
    graph[1].push_back({2, 1});
    graph[1].push_back({4, 5});
    graph[2].push_back({5, 3});
    graph[3].push_back({4, 1});
    graph[4].push_back({5, 2});
    dijkstra(graph, 0);
    return 0;
}