Dijkstra单源最短路径算法是什么

# Dijkstra单源最短路径算法是什么

## 一、算法概述

Dijkstra算法（迪杰斯特拉算法）是由荷兰计算机科学家**艾兹赫尔·戴克斯特拉**（Edsger W. Dijkstra）于1956年提出的经典**单源最短路径算法**。该算法用于解决**带权有向图或无向图**中从单个源点到其他所有顶点的最短路径问题，要求图中**边权值非负**。

### 核心思想
通过**贪心策略**逐步确定从源点到各顶点的最短路径，每次选择当前距离源点最近的未处理顶点，并更新其邻接顶点的最短距离。

## 二、算法原理详解

### 1. 基本概念
- **松弛操作（Relaxation）**：若存在边(u,v)且`d[u] + w(u,v) < d[v]`，则更新`d[v] = d[u] + w(u,v)`
- **优先队列**：用于高效获取当前距离最小的顶点

### 2. 算法步骤
```python
1. 初始化：
   - 距离数组dist[]：dist[src]=0，其余为∞
   - 集合S（已确定最短路径的顶点）
   - 优先队列Q（存放未处理顶点）

2. while Q非空：
   a. 从Q中取出dist最小的顶点u
   b. 将u加入S
   c. 对u的每个邻接顶点v：
      i. 执行松弛操作
      ii. 若dist[v]被更新，则调整Q中v的位置

3. 示例演示（表格+图示）

以如下图为例：

        A
    1/   \2
    B-----C
    3   1

逐步执行过程：

三、时间复杂度分析

不同实现方式的复杂度

其中V为顶点数，E为边数

四、算法正确性证明

关键引理

每次将顶点u加入集合S时，dist[u]已经是源点到u的最短距离。

归纳法证明： 1. 初始时S={s}，显然成立 2. 假设前k次操作都正确，考虑第k+1次选择的顶点u 3. 若存在更短路径P，则P必包含某个不在S中的顶点y 4. 但根据贪心选择，dist[y]≥dist[u]，矛盾

五、代码实现

Python实现（优先队列版）

import heapq

def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    heap = [(0, src)]
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, w in graph[u].items():
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    
    return dist

C++实现（邻接表）

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

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int src) {
    vector<int> dist(graph.size(), INT_MAX);
    dist[src] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.emplace(0, src);
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

六、实际应用场景

典型应用领域

1. 网络路由：OSPF协议中的路由计算
2. 交通导航：地图软件的最短路径规划
3. 机器人路径规划：避开障碍物的最优路径
4. 社交网络分析：影响力传播路径

限制与变种

• 边权为负：需使用Bellman-Ford算法
• 所有顶点对：Floyd-Warshall算法
• A*算法：带启发式函数的改进版

七、与其他算法的对比

八、常见问题解答

Q1：为什么Dijkstra不能处理负权边？

当存在负权边时，已确定最短路径的顶点可能通过负权边获得更短路径，破坏贪心选择性质。

反例：

A -> B (1)
A -> C (2)
B -> C (-2)

按Dijkstra会错误认为A->C最短为2，实际应为A->B->C=-1

Q2：如何记录具体路径？

维护prev[]数组，在松弛操作时更新前驱节点，最后反向追溯。

Q3：算法是否适用于无向图？

可以，将无向边视为两条反向的有向边即可。

九、扩展阅读

1. 原始论文：Dijkstra, E.W. (1959). “A note on two problems in connexion with graphs”
2. 优化方向：双向Dijkstra、ALT启发式
3. 并行实现：GPU加速版本

本文共计约2000字，完整覆盖了Dijkstra算法的核心原理、实现细节和应用场景。如需进一步了解具体实现或数学证明，建议参考《算法导论》第24章相关内容。 “`

该文章采用Markdown格式编写，包含： 1. 多级标题结构 2. 算法步骤伪代码 3. 时间复杂度对比表格 4. 实际代码示例（Python/C++） 5. 应用场景列表 6. 常见问题解答 7. 数学公式和证明 8. 可视化示例

可通过添加更多示例图或实际应用案例进一步扩展内容。