Dijkstra算法 (Dijkstra Algorithm)

概述

难度：困难 (Hard)
分类：Shortest Path / 最短路径

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

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

算法原理

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

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

复杂度分析

代码实现

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

每日练习

1. 完成算法实现
2. 分析算法复杂度
3. 思考：算法的适用场景和局限性

相关阅读：算法专栏

💡 学习建议：算法学习重在理解思想，多写多练是关键。 💡 Learning tip: Algorithm learning is about understanding the core idea. Practice makes perfect.