Python中使用Dijkstra算法求最短路径
Dijkstra算法是一种经典的最短路径算法，使用广泛。它是从一个源点到其他所有点的最短路径算法，主要特点是通过边实现松弛操作，实际上是一种贪心算法。下面我们通过Python代码来实现Dijkstra算法。
假设有一张加权有向图，使用邻接矩阵表示：
1 2 3 4 5
----------------------------------
1 | 0 10 INF 30 100
2 | INF 0 50 INF INF
3 | INF INF 0 INF 10
4 | INF INF 20 0 60
5 | INF INF INF INF 0
对于每个节点，我们需要记录它到起点的距离，以及是否已经被访问过。在代码中我们使用两个列表来保存这些信息：
INF = 9999 # 用来表示无穷大 # 初始图的邻接矩阵 graph = [ [0, 10, INF, 30, 100], [INF, 0, 50, INF, INF], [INF, INF, 0, INF, 10], [INF, INF, 20, 0, 60], [INF, INF, INF, INF, 0], ] # 节点的数量 n = len(graph) # 起点的编号为1 start_node = 1 # 初始每个节点的距离都为无穷大 distances = [INF for _ in range(n)] # 初始每个节点都未被访问 visited = [False for _ in range(n)]
接下来我们需要实现Dijkstra算法的主体部分。具体来说，每次从未被访问的节点中选择一个到起点距离最短的节点作为当前节点，并且将其标记为已访问。然后，对于这个节点的每个邻居，我们需要进行松弛操作，即更新到起点的距离。
# 初始化起点的距离为0 distances[start_node-1] = 0 for i in range(n): # 找到当前未被访问的到起点距离最近的节点 min_dist = INF current_node = None for j in range(n): if not visited[j] and distances[j] < min_dist: min_dist = distances[j] current_node = j if current_node is None: break # 所有节点都已被访问，退出循环 # 标记当前节点已被访问 visited[current_node] = True # 对于当前节点的每个邻居，进行松弛操作 for j in range(n): if not visited[j] and graph[current_node][j] != INF: new_distance = distances[current_node] + graph[current_node][j] if new_distance < distances[j]: distances[j] = new_distance
最后，我们可以输出每个节点到起点的最短距离：
for i in range(n): print("Node {}: {}".format(i+1, distances[i]))
输出结果如下：
Node 1: 0 Node 2: 10 Node 3: 50 Node 4: 30 Node 5: 60
这就是使用Python实现Dijkstra算法求最短路径的完整代码。如果需要使用字符串作为范例，可以将邻接矩阵中的数字替换为字符串即可。
相关文章