Dijkstra最短路径算法 简单代码

以下是一个简单的Dijkstra最短路径算法的示例代码，假设有一个无向图：

       7       2
   A------B------C
    \     |     /
     \    |    /
   3  \   |   /  4
       \  |  /
         \| /
          D

其中，每条边表示两个节点之间的距离。我们要求从节点A到其他节点的最短距离：

import math

# 定义无穷大
inf = math.inf

# 定义图的邻接矩阵
graph = [
    [0, 7, 3, inf],
    [7, 0, 2, 4],
    [3, 2, 0, 5],
    [inf, 4, 5, 0]
]

# 定义起点和终点
start, end = 0, 3

# 初始化节点的最短距离和最短路径
distances = [inf] * len(graph)
distances[start] = 0
paths = [[] for _ in range(len(graph))]
paths[start] = [start]

# 查找最短路径
visited = set()
while end not in visited:
    current = min((distance, node) for node, distance in enumerate(distances) if node not in visited)[1]
    visited.add(current)
    for neighbor, distance in enumerate(graph[current]):
        if distance != 0 and neighbor not in visited:
            new_distance = distances[current] + distance
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                paths[neighbor] = paths[current] + [neighbor]

# 输出结果
print(f"从节点{chr(ord('A')+start)}到节点{chr(ord('A')+end)}的最短距离为{distances[end]}，最短路径为{'-'.join(chr(ord('A')+i) for i in paths[end])}")

运行此代码将输出从节点A到节点D的最短距离和最短路径。您可以根据需要进行修改和扩展。