Python 中单源最短路径问题的贪心解法

import sys

def dijkstra(graph, start_node):
    visited = set() # 记录已确定最短路径的节点
    distance = {start_node: 0} # 记录到起点的距离，初始为 0
    nodes = set(graph.keys()) # 所有节点集合
    while nodes - visited:
        # 选择距离最小的节点进行更新
        current_node = min((node for node in nodes - visited), key=lambda x: distance.get(x, sys.maxsize))
        visited.add(current_node)
        # 更新邻近节点到起点的距离
        for neighbor, weight in graph[current_node].items():
            if neighbor not in visited:
                new_distance = distance.get(current_node, sys.maxsize) + weight
                if new_distance < distance.get(neighbor, sys.maxsize):
                    distance[neighbor] = new_distance
    return distance

# 构建图的邻接矩阵
graph = {
    "pidancode.com": {"皮蛋编程": 2, "Python": 5},
    "皮蛋编程": {"pidancode.com": 2, "Python": 1},
    "Python": {"pidancode.com": 5, "皮蛋编程": 1, "程序员": 3},
    "程序员": {"Python": 3, "Java": 4},
    "Java": {"程序员": 4}
}

start_node = "pidancode.com"
distance = dijkstra(graph, start_node)
print("最短路径距离：", distance)

最短路径距离： {'pidancode.com': 0, '皮蛋编程': 2, 'Python': 3, '程序员': 6, 'Java': 10}