用 Python 实现 Dijkstra 算法：一步一步的教程

为什么要学习 Dijkstra 算法？

Dijkstra 是在网络中寻找两点之间最短路径的首选算法，应用广泛。它是计算机科学与图论中的基础。理解并学会实现它，将为更高级的图算法与应用奠定基础。

它还是学习一种重要问题求解思路的途径——贪心算法，即在每一步都基于当前信息做出最优选择。

这一技能可迁移到其他优化算法。Dijkstra 算法并非所有场景下都最高效，但在解决“最短距离”问题时，它是一个很好的基线。

示例包括：

• GPS 导航系统寻找最快路线
• 计算机网络中的数据包路由
• 配送服务为效率优化路线
• 社交网络（推荐关系）
• 金融（寻找最优投资路径）
• 项目管理（寻找最高效的工作流程）

即使您对上述领域并不感兴趣，用 Python 实现 Dijkstra 算法也能让您练习以下重要概念：

• Python 类
• 字典推导式
• 列表推导式
• 优先队列

与图相关的关键概念

要在 Python 中实现 Dijkstra 算法，我们需要回顾图论中的几个基本概念。首先是图本身：

图是由节点（顶点）与边构成的集合。节点表示网络中的实体或点，边表示它们之间的连接或关系。

图可以是加权或非加权。非加权图中，所有边的权重相同（通常设为 1）。在加权图中（正如其名），每条边都有一个权重，常表示成本、距离或时间。

本教程将使用加权图，因为 Dijkstra 算法需要加权图。

图中的路径指由边连接的一系列节点，从特定起点到终点。在本教程中我们关心的是最短路径，即总权重（距离、成本等）最小的那条路径。

用可视化方式解释 Dijkstra 算法

在接下来的教程中，我们将使用刚才看到的最后一个图：

让我们用 Dijkstra 算法在至少七条可能路径中，找出点 B 与 F 之间的最短路径。起初我们先用可视化方式完成此任务，随后再用代码实现。

首先，如下初始化算法：

1. 将 B 设为根（源）节点。
2. 将 B 与所有其他节点之间的距离设为无穷大，作为它们初始的暂定距离值。将 B 自身的值设为 0，因为到自己的距离为 0：

然后，我们迭代执行以下步骤：

1. 选择值最小的节点作为“当前节点”，并访问其所有相邻节点。访问每个相邻节点时，从源节点出发，按相邻边的权重更新它们的暂定值（由无穷大更新为具体值）。
2. 当当前节点的所有相邻节点都已访问后，将当前节点标记为“已访问”。一旦节点被标记为“已访问”，它的值就是到目标的最短路径值。
3. 算法回到第 1 步，选择值最小的节点。

在我们的图中，B 有三个邻居——A、D 和 E。让我们从根节点开始依次访问它们，并根据它们的边权更新其值（迭代 1）：

在迭代 2 中，我们再次选择值最小的节点，这次是 E。它的邻居是 C、D 和 G。B 已被排除，因为我们已经访问过它。让我们更新 E 的邻居的值：

我们将 C 的值设为 5.6，因为它的值是从 B 到 C 的权重累计和。G 同理。不过，如果您注意到，D 的值仍为 3.5，而不是像其他节点那样应为 3.5 + 2.8 = 6.3。

规则是：如果新的累计和大于该节点当前的值，我们就不更新，因为该节点的当前值已经记录了到根的最短距离。在本例中，D 当前的 3.5 就是它到 B 的最短距离，因为它们是邻居。

我们以此方式继续，直到所有节点都被访问。届时，我们就得到了从 B 到每个节点的最短距离，可以直接查看 B 到 F 的值。

总结而言，步骤是：

1. 用源节点初始化图：源节点取值为 0，其他节点为无穷大。从源节点作为“当前节点”开始。
2. 访问当前节点的所有邻居，并将其值更新为从源节点起的权重累计和（距离）。如果某个邻居当前值小于累计和，则保持不变。将“当前节点”标记为已完成。
3. 将尚未完成且取值最小的节点标记为“当前节点”。
4. 重复第 2、3 步，直到所有节点都完成。

在 Python 中逐步实现 Dijkstra 算法

现在，为了加深您对 Dijkstra 算法的理解，我们将一步步用 Python 来实现。

将图理解为字典

首先，我们需要一种在 Python 中表示图的方式——最常见的选择是使用字典。如果这是我们的图：

我们可以用如下字典表示它：

graph = {
   "A": {"B": 3, "C": 3},
   "B": {"A": 3, "D": 3.5, "E": 2.8},
   "C": {"A": 3, "E": 2.8, "F": 3.5},
   "D": {"B": 3.5, "E": 3.1, "G": 10},
   "E": {"B": 2.8, "C": 2.8, "D": 3.1, "G": 7},
   "F": {"G": 2.5, "C": 3.5},
   "G": {"F": 2.5, "E": 7, "D": 10},
}
技术支持

字典的每个键是一个节点，每个值是一个字典，包含该键的邻居及到邻居的距离。我们的图有七个节点，因此字典必须有七个键。

其他资料通常将上述字典称为邻接表字典（dictionary adjacency list）。接下来我们也沿用这一术语。

1. 创建一个 Graph 类

为使代码更模块化、更易理解，我们将实现一个简单的 Graph 类来表示图。在其内部，它将使用邻接表字典。它还会有一个方法，用于轻松地在两个节点之间添加连接：

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph  # A dictionary for the adjacency list

   def add_edge(self, node1, node2, weight):
       if node1 not in self.graph:  # Check if the node is already added
           self.graph[node1] = {}  # If not, create the node
       self.graph[node1][node2] = weight  # Else, add a connection to its neighbor
技术支持

使用该类，我们可以像这样从零开始迭代构建图：

G = Graph()

# Add A and its neighbors
G.add_edge("A", "B", 3)
G.add_edge("A", "C", 3)

# Add B and its neighbors
G.add_edge("B", "A", 3)
G.add_edge("B", "D", 3.5)
G.add_edge("B", "E", 2.8)

...
技术支持

或者我们可以直接传入一个邻接表字典，这更快捷：

# Use the dictionary we defined earlier
G = Graph(graph=graph)

G.graph
技术支持

{'A': {'B': 3, 'C': 3},
'B': {'A': 3, 'D': 3.5, 'E': 2.8},
'C': {'A': 3, 'E': 2.8, 'F': 3.5},
'D': {'B': 3.5, 'E': 3.1, 'G': 10},
'E': {'B': 2.8, 'C': 2.8, 'D': 3.1, 'G': 7},
'F': {'G': 2.5, 'C': 3.5},
'G': {'F': 2.5, 'E': 7, 'D': 10}}
技术支持

2. 用字典存储源点到各节点的距离

我们再创建一个类方法——这次用于算法本身——shortest_distances：

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   # The add_edge method omitted for space

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       ...
技术支持

在该方法内部，我们首先定义一个包含节点-取值对的字典。每次访问某个节点及其邻居时，该字典都会更新。正如我们在算法的可视化解释中提到的，所有节点的初始值设为无穷大，而源点的值为 0。

当方法编写完成后，会返回这个字典，其中包含从源点到所有节点的最短距离。我们就可以像这样找到从 B 到 F 的距离：

# Sneak-peek - find the shortest paths from B
distances = G.shortest_distances("B")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
技术支持

3. 使用优先队列迭代节点

现在，我们需要一种方式，按照 Dijkstra 算法的规则遍历图中的节点。如果您还记得，在每次迭代中，我们都需要选择取值最小的节点并访问它的邻居。

您可能会说，我们可以直接遍历字典的键：

for node in graph.keys():
   ...
技术支持

这种方法不行，因为它无法根据节点的值进行排序。因此，简单数组无法满足需求。为解决这一问题，我们将使用优先队列。

优先队列类似于常规列表（数组），但每个元素都有一个额外的优先级值。下面是一个示例优先队列：

pq = [(3, "A"), (1, "C"), (7, "D")]技术支持

这个队列包含三个元素——A、C 和 D——每个都有一个决定队列操作顺序的优先级。Python 提供了内置的 heapq 库来处理优先队列：

from heapq import heapify, heappop, heappush技术支持

该库有三个我们关心的函数：

• heapify：将由“优先级-值”对组成的列表转换为优先队列。
• heappush：将带有其优先级的元素加入队列。
• heappop：移除并返回优先级最高（数值最小）的元素。

pq = [(3, "A"), (1, "C"), (7, "D")]

# Convert into a queue object
heapify(pq)

# Return the highest priority value
heappop(pq)
技术支持

(1, 'C')技术支持

如您所见，将 pq 用 heapify 转为队列后，我们就能按优先级取出 C。我们再试着推入一个值：

heappush(pq, (0, "B"))

heappop(pq)
技术支持

(0, 'B')技术支持

队列已根据新元素的优先级正确更新，因为 heappop 返回了优先级为 0 的新元素。

注意，一旦我们弹出一个元素，它将不再属于队列。

现在回到我们的算法，在初始化好 distances 后，我们创建一个新的优先队列，该队列初始只包含源节点：

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()
技术支持

pq 中每个元素的优先级就是它的当前取值。我们还初始化一个空集合来记录已访问的节点。

4. 用 while 循环实现 Dijkstra 算法

现在，我们使用 while 循环开始遍历所有未访问的节点：

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()

       while pq:  # While the priority queue isn't empty
           current_distance, current_node = heappop(
               pq
           )  # Get the node with the min distance

           if current_node in visited:
               continue  # Skip already visited nodes
           visited.add(current_node)  # Else, add the node to visited set
技术支持

当优先队列不为空时，我们不断弹出优先级最高（数值最小）的节点，并将其取值与名称分别赋给 current_distance 与 current_node。如果 current_node 已在 visited 中，我们就跳过；否则将其标记为已访问，然后转而访问其邻居：

while pq:  # While the priority queue isn't empty
   current_distance, current_node = heappop(pq)

   if current_node in visited:
       continue 
   visited.add(current_node)

   for neighbor, weight in self.graph[current_node].items():
       # Calculate the distance from current_node to the neighbor
       tentative_distance = current_distance + weight
       if tentative_distance < distances[neighbor]:
           distances[neighbor] = tentative_distance
           heappush(pq, (tentative_distance, neighbor))

return distances
技术支持

对于每个邻居，我们通过将连接边的权重加到当前节点的值上，计算从当前节点到该邻居的暂定距离。然后检查该距离是否小于该邻居在 distances 中的距离。如果是，则更新 distances 字典，并将带有暂定距离的邻居加入优先队列。

就是这样！我们已经实现了 Dijkstra 算法。来测试一下：

G = Graph(graph)

distances = G.shortest_distances("B")
print(distances, "\n")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
技术支持

{'A': 3, 'B': 0, 'C': 5.6, 'D': 3.5, 'E': 2.8, 'F': 9.1, 'G': 9.8}

The shortest distance from B to F is 9.1
技术支持

因此，从 B 到 F 的距离是 9.1。但等等：这条路径是哪一条？

5. 构造最短路径

到目前为止，我们只有最短距离而非路径，使得我们的图看起来像这样：

要从计算得到的最短距离构造最短路径，我们可以从目标点开始回溯。对于连接到 F 的每条边，分别相减其权重：

1. 9.1–3.5 = 5.6
2. 9.1–2.5 = 6.5

然后查看这些结果是否与 F 的邻居的取值相匹配。只有 5.6 与 C 的值匹配，这意味着 C 在最短路径上。

我们对 C 的邻居 A 和 E 再重复一次：

1. 5.6–3 = 2.6
2. 5.6–2.8 = 2.8

由于 2.8 与 E 的值相匹配，它也在最短路径上。E 也是 B 的邻居，因此 B 与 F 之间的最短路径是 BECF。

让我们把这一过程的实现添加到我们的类中。代码本身与上述解释略有不同，因为它会找出 B 与所有其他节点之间的最短路径，而不仅仅是 F。

此外，它是反向完成的，但思路相同。

将以下代码添加到 shortest_distances 方法的末尾，并删除旧的 return 语句：

predecessors = {node: None for node in self.graph}

for node, distance in distances.items():
   for neighbor, weight in self.graph[node].items():
       if distances[neighbor] == distance + weight:
           predecessors[neighbor] = node

return distances, predecessors
技术支持

当代码运行完成时，predecessors 字典将包含参与到源点最短路径中的每个节点的直接父节点。我们来试试：

G = Graph(graph)

distances, predecessors = G.shortest_distances("B")

print(predecessors)
技术支持

{'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}技术支持

首先，让我们用 predecessors 字典从 F 开始回溯，手动找出最短路径：

# Check the predecessor of F
predecessors["F"]
技术支持

'C'  # It is C技术支持

# Check the predecessor of C
predecessors["C"]
技术支持

'E'  # It is E技术支持

# Check the predecessor of E
predecessors["E"]
技术支持

'B'  # It is B技术支持

就是这样！该字典正确告诉我们，B 与 F 之间的最短路径是 BECF。

不过我们是半手动完成的。我们希望有一个方法，能从任意源点到任意目标点，基于 predecessors 字典自动返回最短路径。我们将该方法定义为 shortest_path（将其添加到类的末尾）：

def shortest_path(self, source: str, target: str):
   # Generate the predecessors dict
   _, predecessors = self.shortest_distances(source)

   path = []
   current_node = target

   # Backtrack from the target node using predecessors
   while current_node:
       path.append(current_node)
       current_node = predecessors[current_node]

   # Reverse the path and return it
   path.reverse()

   return path
技术支持

通过调用 shortest_distances 函数，我们生成 predecessors 字典。随后启动一个 while 循环，每次迭代都从当前节点回溯到其父节点，直到到达源节点。然后我们反转并返回该列表，即从源点到目标点的路径。

测试一下：

G = Graph(graph)

G.shortest_path("B", "F")
技术支持

['B', 'E', 'C', 'F']技术支持

可以！再试一个：

G.shortest_path("A", "G")技术支持

['A', 'C', 'F', 'G']技术支持

一切顺利。

结语

在本教程中，我们学习了图论中最基础的算法之一——Dijkstra。它常用于在类图结构中寻找两点之间的最短路径。由于其简单性，它在多个行业中都有应用，例如：

• 物流与交通运输
• 网络与电信
• 制造与机器人
• 金融与投资
• 城市规划

希望用 Python 实现 Dijkstra 算法能够激发您对精彩图算法世界的兴趣。如果您想进一步学习，我强烈推荐以下资源：

• Introduction to Network Analysis in Python 课程
• Data Structures And Algorithms in Python 课程