🧮 Dijkstra算法 (Dijkstra Algorithm)

难度 / Difficulty: 困难 (Hard)
分类 / Category: 最短路径 (Shortest Path)
时间复杂度 / Time Complexity: O((V + E) log V)
空间复杂度 / Space Complexity: O(V)

📖 算法简介 / Introduction

Dijkstra 算法是用于计算单源最短路径的贪心算法，适用于非负权边。

Dijkstra is a greedy algorithm for single-source shortest path in graphs with non-negative edge weights.

💡 算法原理 / Principle

从起点开始，每次选择未处理节点中距离最小的，加入已处理集合，更新邻居距离。

Starting from source, each time select the closest unprocessed node, add to processed set, update neighbor distances.

📝 代码实现 / Implementation

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

✨ 示例 / Example

在带权Graph中计算从A到所有节点的最短距离。

Computing shortest distances from node A to all nodes in a weighted graph.

🎯 适用场景 / Scenarios

导航路线规划, 网络路由, 航班价格优化

Navigation routing, Network routing, Flight price optimization

🔄 扩展阅读 / Further Reading

• 建议在 LeetCode 或 HackerRank 上刷相关题目
• 尝试自己实现非递归版本
• 对比其他同类型算法的性能差异