Dijkstra（迪杰斯特拉算法）是什么？

Dijkstra算法 是一种用于在 带权图（Weighted Graph） 中计算 单源最短路径（Single-Source Shortest Path, SSSP） 的经典算法。它由荷兰计算机科学家 艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra） 在1956年提出，广泛应用于网络路由、地图导航、交通规划等领域。

1. 核心思想

Dijkstra算法的核心是 贪心策略（Greedy Algorithm），逐步找到从 起点（Source） 到所有其他节点的最短路径。
关键特点：

• 适用条件：边权值 非负（不能有负权边）。
• 时间复杂度：
  • 普通实现：O(V2)O(V2)（VV 是顶点数）。
  • 优先队列优化：O(E+Vlog⁡V)O(E+VlogV)（EE 是边数）。

2. 算法步骤

输入

• 一个带权图 G=(V,E)G=(V,E)（VV 是顶点集合，EE 是边集合）。
• 一个 起点（Source） ss。

输出

• 从 ss 到所有其他顶点的最短距离。

步骤

1. 初始化：
   • 设置 dist[s] = 0（起点到自己的距离为0）。
   • 其他所有顶点 dist[v] = ∞（初始认为不可达）。
   • 创建一个 优先队列（Priority Queue）（或最小堆），存储 (距离, 顶点) 对。
2. 循环处理：
   • 从队列中取出当前 距离最小的顶点 uu（即当前已知的最短路径）。
   • 遍历 uu 的所有邻居 vv：
     • 计算 松弛（Relaxation）：

如果 dist[u]+w(u,v)<dist[v],则更新 dist[v]=dist[u]+w(u,v)

（其中 w(u,v)w(u,v) 是边 u→vu→v 的权重）

1. • • 如果更新成功，将 (新dist[v], v) 加入队列。
2. 终止条件：
   • 当队列为空时，算法结束，dist[] 存储的就是最短路径。

3. 示例

给定图（起点为 A）

text

复制

下载

        A

      / | \

     1  3  2

    /   |   \

   B    C    D

    \   |   /

     4  1  5

      \ | /

        E

求 A 到所有其他顶点的最短路径。

执行过程

步骤	当前顶点	更新邻居	dist（A,B,C,D,E）
1	A	B(1), C(3), D(2)	[0, 1, 3, 2, ∞]
2	B	E(1+4=5)	[0, 1, 3, 2, 5]
3	D	E(2+5=7) → 不更新（5 < 7）	[0, 1, 3, 2, 5]
4	C	E(3+1=4) → 更新 E	[0, 1, 3, 2, 4]
5	E	无邻居可更新	算法结束

最终结果：

• A → A: 0
• A → B: 1
• A → C: 3
• A → D: 2
• A → E: 4

4. 代码实现（C++）

#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;

        int current_dist = pq.top().first;

        pq.pop();



        // 如果当前距离大于已知最短距离，跳过

        if (current_dist > dist[u]) continue;



        // 遍历所有邻居

        for (auto [v, weight] : graph[u]) {

            if (dist[u] + weight < dist[v]) {

                dist[v] = dist[u] + weight;

                pq.push({dist[v], v});

            }

        }

    }



    // 输出结果

    for (int i = 0; i < n; i++) {

        cout << "Distance from " << start << " to " << i << ": " << dist[i] << endl;

    }

}



int main() {

    // 示例图（邻接表表示）

    vector<vector<pair<int, int>>> graph = {

        {{1, 1}, {2, 3}, {3, 2}},  // A -> (B,1), (C,3), (D,2)

        {{4, 4}},                   // B -> (E,4)

        {{4, 1}},                   // C -> (E,1)

        {{4, 5}},                   // D -> (E,5)

        {}                          // E 无出边

    };



    dijkstra(graph, 0); // 从 A（0）开始计算

    return 0;

}

输出：

text

Distance from 0 to 0: 0

Distance from 0 to 1: 1

Distance from 0 to 2: 3

Distance from 0 to 3: 2

Distance from 0 to 4: 4

5. 常见问题

Q1: Dijkstra 能否处理负权边？

❌ 不能！
如果存在负权边，Dijkstra 可能会得到错误结果（因为它基于贪心策略，认为当前最短路径不会再被更新）。
✅ 替代算法：Bellman-Ford 或 SPFA。

Q2: Dijkstra 和 BFS 的区别？

• BFS：适用于无权图（所有边权重相同），按层遍历。
• Dijkstra：适用于带权图（权重非负），优先走当前最短路径。

Q3: 如何优化 Dijkstra？

• 优先队列（堆优化）：时间复杂度从 O(V2)O(V2) 降到 O(E+Vlog⁡V)O(E+VlogV)。
• 斐波那契堆：理论更优，但实现复杂。

6. 应用场景

• 地图导航（如 Google Maps 计算最短路线）。

• 网络路由（如 OSPF 协议）。
• 交通规划（地铁/公交换乘最优路径）。
• 游戏 AI（NPC 寻路）。

总结

特性	Dijkstra 算法
用途	单源最短路径（非负权图）
时间复杂度	O(E+Vlog⁡V)O(E+VlogV)（堆优化）
限制	不能有负权边
优化方式	优先队列（最小堆）

如果问题涉及 非负权图 + 最短路径，Dijkstra 是最优选择！ 🚀