我来详细介绍一下迪杰斯特拉算法（Dijkstra’s Algorithm）。

算法概述

迪杰斯特拉算法是用于在带权有向图中寻找单源最短路径的经典算法，由荷兰计算机科学家艾兹格·迪杰斯特拉于1956年提出。

核心思想

采用贪心策略，逐步确定从源点到其他各顶点的最短路径，要求所有边的权值非负。

算法步骤

基础版本（使用数组）

1. 初始化：
   - 创建距离数组dist[]，设置源点距离为0，其他顶点为∞
   - 创建访问标记数组visited[]，全部设为False
   - 创建前驱节点数组prev[]，用于记录路径

2. 重复以下步骤直到所有顶点都被访问：
   a. 从未访问顶点中选择dist值最小的顶点u
   b. 标记u为已访问
   c. 对于u的每个邻接顶点v：
      如果 dist[u] + weight(u,v) < dist[v]：
         更新 dist[v] = dist[u] + weight(u,v)
         更新 prev[v] = u

优化版本（使用优先队列/最小堆）

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    prev = [-1] * n
    heap = [(0, start)]  # (距离, 顶点)
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        
        # 如果当前距离大于已知最短距离，跳过
        if current_dist > dist[u]:
            continue
            
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(heap, (new_dist, v))
    
    return dist, prev

时间复杂度分析

数据结构 时间复杂度 空间复杂度 适用场景
邻接矩阵 + 数组 O(V²) O(V) 稠密图
邻接表 + 二叉堆 O((V+E)logV) O(V+E) 稀疏图
邻接表 + 斐波那契堆 O(VlogV + E) O(V+E) 理论最优

算法特点

优点：

1. ✅ 效率高：在非负权图中是最快的单源最短路径算法之一
2. ✅ 确定性：总能找到最短路径（权值非负时）
3. ✅ 灵活性：可同时得到源点到所有其他顶点的最短路径

局限性：

1. ❌ 不能处理负权边：可能得到错误结果
2. ❌ 非负权图专用：遇到负权需用Bellman-Ford算法
3. ❌ 单源问题：求所有点对最短路径时效率不如Floyd-Warshall

应用实例

示例图：

        6
    A ----- B
    | \     |
   2|   \1  |3
    |     \ |
    C ----- D
        1

执行过程（从A出发）：

步骤 已确定顶点 距离数组[A,B,C,D] 说明
初始 A [0,∞,∞,∞] 源点A距离为0
1 A [0,6,2,1] 选择A，更新邻居
2 A,D [0,4,2,1] 选距离最小的D，经D到B更短
3 A,D,C [0,3,2,1] 选C，经C到B更短
4 全部 [0,3,2,1] 完成

最短路径：

· A→B: A→D→B (3)
· A→C: A→C (2)
· A→D: A→D (1)

常见变体和优化

1. 双向Dijkstra：从起点和终点同时搜索，加速查询
2. A*算法：加入启发式函数，用于已知目标的情况
3. 使用索引优先队列：提高堆操作效率
4. 并行化实现：利用多核处理器加速

实际应用场景

· 🗺️ 地图导航系统（GPS）
· 🌐 网络路由协议（OSPF）
· 🚦 交通流量优化
· ⚡ 电路布线设计
· 🎮 游戏AI路径规划

注意事项

1. 确保图中没有负权边
2. 对于大规模图，考虑使用更高效的数据结构
3. 如果需要频繁查询，可以考虑预处理或使用更高级的算法
4. 在动态图中（边权会变化），需要特殊处理

这个算法是图论和算法课程中的核心内容，理解它对于学习更复杂的最短路径算法（如Bellman-Ford、Floyd-Warshall）很有帮助。