auto_ai 知识库

Appearance

Dijkstra 算法用于求解带权有向图中单源最短路径问题，从一个源点出发，求到所有其他顶点的最短距离。基于贪心思想，每次选择当前距离最小的未确定顶点，用它松弛相邻顶点。适用于边权非负的图。

定义与核心原理 ​

贪心策略 ​

  1. 维护一个距离数组 dist[]，dist[v] 表示源点到 v 的当前最短距离
  2. 每次从未确定的顶点中选择 dist 最小的顶点 u，标记为"已确定"
  3. 用 u 松弛其邻接顶点 v：dist[v] = min(dist[v], dist[u] + weight(u,v))
  4. 重复直到所有顶点确定

为什么正确 ​

因为边权非负，每次选出的 dist 最小的顶点，其最短距离不可能再被其他未确定顶点更新（其他路径都更长）。

操作步骤 ​

优先队列（堆优化）实现 ​

cpp
vector<int> dijkstra(int n, vector<vector<pair<int,int>>>& adj, int start) {
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // {距离, 顶点}
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 过期记录，跳过
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

完整执行示例 ​

图（顶点 1~5，源点为 1）：

边：1→4(2), 1→3(5), 1→5(2), 4→2(6), 4→3(2), 5→3(1), 3→2(2)

优先队列操作过程：

出队距离操作入队队列状态
{0,1}0松弛4,3,5{2,4},{5,3},{2,5}{2,4},{2,5},{5,3}
{2,4}2松弛2→8, 3→4{8,2},{4,3}{2,5},{4,3},{5,3},{8,2}
{2,5}2松弛3→3{3,3}{3,3},{4,3},{5,3},{8,2}
{3,3}3松弛2→5{5,2}{4,3},{5,2},{5,3},{8,2}
{4,3}4d>dist[3]=3，跳过-{5,2},{5,3},{8,2}
{5,3}5d>dist[3]=3，跳过-{5,2},{8,2}
{5,2}5无出边-{8,2}
{8,2}8d>dist[2]=5，跳过-空

最终最短距离：

顶点距离路径
10-
251→5→3→2
331→5→3
421→4
521→5

复杂度分析 ​

实现方式时间复杂度适用场景
朴素（数组找最小）O(V²)稠密图
优先队列（堆优化）O(E log V)稀疏图
空间O(V+E)邻接表

实践应用 ​

  • 地图导航：两点间最短路径
  • 网络路由：OSPF 协议的最短路径优先
  • 游戏 AI：寻路算法（A* 的基础）
  • 社交网络：最短关系链

常见误区 ​

  1. 负权边：Dijkstra 不能处理负权边，需用 Bellman-Ford 或 SPFA
  2. 忘记跳过过期记录：优先队列中可能有同一顶点的多条记录，需用 if (d > dist[u]) continue 跳过
  3. 源点初始化：dist[start] = 0，其余为无穷大，不要全部初始化为 0
  4. 无向图处理：无向图的每条边要在邻接表中添加两次

一句话总结 ​

Dijkstra 是贪心：每轮取 dist 最小的未确定点松弛邻居，堆优化后 O(E log V)；边权必须非负，且要用 if (d > dist[u]) continue 跳过过期记录。

相关概念 ​