Dijkstra 算法是一种用于在加权图中找到单源最短路径的算法。在 LeetCode 中，有许多关于图论的问题可以使用 Dijkstra 算法来解决。以下是一些使用 Dijkstra 算法的 LeetCode 图论问题示例：

示例问题

  1. 最短路径问题 I - 矩阵中的最短路径 (LeetCode 127)

    • 查看题目
    • 题目描述：在一个有向图中，找到两个节点之间的最短路径。

  2. 最短路径问题 II - 矩阵中的所有最短路径 (LeetCode 743)

    • 查看题目
    • 题目描述：在一个有向图中，找到所有节点之间的最短路径。

Dijkstra 算法步骤

  1. 初始化节点距离表，将起点距离设为 0，其他节点设为无穷大。
  2. 选择一个未访问的节点，将其距离设为当前已知的最近距离。
  3. 更新相邻节点的距离，如果找到更短的路径，则更新距离表。
  4. 重复步骤 2 和 3，直到所有节点都被访问过。

示例代码

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)
        for w, neighbor in graph[node].items():
            if dist[neighbor] > d + w:
                dist[neighbor] = d + w
                heapq.heappush(pq, (d + w, neighbor))
    return dist

总结

Dijkstra 算法是解决图论问题的重要工具，特别是在寻找最短路径方面。通过 LeetCode 上的练习，可以更好地理解和应用 Dijkstra 算法。

Dijkstra Algorithm