Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

The algorithm exists in many variants; Dijkstra’s original variant found the shortest path between two nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Dijkstra’s algorithm

之前，在BFS中我们解决了寻找最短路径的问题，但是在BFS中的边是不带权重的，我们找的最短路径即段数最少的。如果带上了权重，我们需要使用Dijkstra算法。主要包括四个步骤：

  1. 找出“最便宜”的节点，即可在最短时间内到达的节点。
  2. 更新该节点的邻居的开销。
  3. 重复这个过程直到对每个节点都这样做了。
  4. 计算最终路径。

术语

Dijkstra算法使用之前先澄清一些术语：

  1. Dijkstra算法用于每条边都有关联数字的图，这些数字被称为权重。
  2. 带权重的图称为加权图，不带权重的图称为非加权图。
  3. 计算非加权图的最短路径使用BFS，计算加权图中的最短路径使用Dijkstra。
  4. 图可能还有环，即可以在某个节点走一圈后回到这个节点。
  5. 之前介绍的无向图意味着彼此指向对方，实际上就是环，无向图中每条边都是一个环。
  6. Dijkstra只适用于有向无环图（directed acyclic graph，DAG）

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    # 遍历所有节点
    for node in costs:      
       cost = costs[node]
       # 如果打枊前节点开销更低且未处理过
       if cost < lowest_cost and node not in processed:
           # 将其视为开销最低的节点
           lowest_cost = cost
           lowest_cost_node = node
    return lowest_cost_node

# 在未处理的节点中找出开销最小的节点
node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    # 遍历当前节点的所有邻居
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    # 找出接下来要处理的节点，并循环
    node = find_lowest_cost_node(costs)

备注：如果图中包含负权边，可以使用贝尔曼-福德算法。

参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著