Dijkstra 算法 是一种用于求解 单源最短路径问题 的经典算法。它可以有效地计算从一个源节点到其他所有节点的最短路径，并且能够处理带权图。这个算法由 Edsger W. Dijkstra 在 1956 年提出，并在 1959 年出版。

问题描述：

给定一个带权有向图（权值可能是正数），找到从一个源节点到图中所有其他节点的最短路径。

基本思想：

Dijkstra 算法使用贪心策略，通过不断扩展当前最短路径集合来求解最短路径。每次选取一个距离源节点最近的未访问节点，更新与该节点相邻的所有节点的最短路径，直到找到所有节点的最短路径。

算法步骤：

  1. 初始化：
    • 对于每个节点 v，设置其到源节点的距离为无穷大 ∞，只有源节点 S 的距离为 0。
    • 将所有节点标记为未访问，源节点的距离设置为 0。
  2. 选择最小距离的节点：
    • 从未访问的节点中，选择一个距离源节点最小的节点 u（即最短路径）。
    • 标记该节点为已访问，表示该节点的最短路径已经找到。
  3. 更新邻接节点的距离：
    • 对于节点 u 的每个邻接节点 v，检查是否可以通过 u 来更新 v 的最短路径。如果 distance[u] + weight(u, v) < distance[v]，则更新 v 的最短路径。
  4. 重复上述步骤：
    • 重复选择最小距离节点和更新邻接节点的距离，直到所有节点都被访问过。
  5. 返回结果：
    • 最终，源节点到每个其他节点的最短路径即为结果。

算法伪代码：

function Dijkstra(Graph, source):
    dist[source] = 0
    for each vertex v in Graph:
        if v ≠ source:
            dist[v] = ∞
        prev[v] = undefined
    Q = all vertices in Graph
    
    while Q is not empty:
        u = vertex in Q with smallest dist[u]
        remove u from Q
        
        for each neighbor v of u:
            alt = dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u

    return dist, prev
  • dist[u]：源节点到节点 u 的当前最短路径。
  • prev[u]：表示到达节点 u 的前驱节点，用于路径重建。
  • Q：表示待处理的节点集合。

时间复杂度：

  • 使用 邻接矩阵 表示图时，算法的时间复杂度为 O(V²)，其中 V 是图中节点的数量。
  • 使用 邻接表 并结合 优先队列（如二叉堆）来优化选择最小距离节点的过程，时间复杂度可以降低到 O((V + E) log V)，其中 E 是图中的边数。

适用条件：

  • Dijkstra 算法要求图中的所有边权为 非负，即图不能有负权边。如果图中有负权边，可以使用 Bellman-Ford 算法 或者 Floyd-Warshall 算法。

例子：

假设有以下图：

         10
    A ------------ B
     |              |
     |              |
    5|             2|
     |              |
    D ------------ C
         3
  1. 初始：
    • A 的距离为 0，其他节点为无穷大。
    • dist[A] = 0, dist[B] = ∞, dist[C] = ∞, dist[D] = ∞
  2. 选取 A，更新 A 的邻接节点 B 和 D：
    • dist[B] = 10, dist[D] = 5
  3. 选取 D（距离最小），更新 D 的邻接节点 C：
    • dist[C] = 5 + 3 = 8
  4. 选取 D 或 C，再选取 B，更新 B 的邻接节点 C：
    • dist[C] = 8（已经是最小）

最终，最短路径为：

  • A -> D (距离 5)
  • A -> B (距离 10)
  • A -> C (距离 8)

Python 实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，所有节点的距离设为无穷大
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 使用堆来优化选择最小距离的节点
    priority_queue = [(0, start)]  # (距离, 节点)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 如果当前距离大于已知最短距离，则跳过
        if current_distance > distances[current_node]:
            continue

        # 更新邻接节点的距离
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            # 如果找到更短的路径，更新并推入优先队列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


# 示例图：邻接表表示法
graph = {
    'A': [('B', 10), ('D', 5)],
    'B': [('C', 2)],
    'C': [('D', 3)],
    'D': [('C', 8)]
}

start = 'A'
distances = dijkstra(graph, start)
print(distances)

输出结果：

{'A': 0, 'B': 10, 'C': 8, 'D': 5}

总结：

  • Dijkstra 算法 是一种高效的算法，用于解决单源最短路径问题，特别适合用于带权图（权值非负）的路径计算。
  • 它采用 贪心策略，每次选择当前最短的节点进行扩展，从而逐步求解最短路径。
  • 该算法最适用于 无负权边 的图。如果图中有负权边，则需要使用其他算法（如 Bellman-Ford 算法）。