动态规划 / 最短路

# 依赖: 标准库 heapq
import heapq

def dijkstra(graph, source):
    if any(w < 0 for edges in graph.values() for w in edges.values()):
        raise ValueError('Dijkstra 不支持负权边')
    dist = {source: 0.0}
    prev = {}
    pq = [(0.0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph.get(u, {}).items():
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v], prev[v] = nd, u
                heapq.heappush(pq, (nd, v))
    return dist, prev

graph = {'A': {'B': 1.0, 'C': 4.0}, 'B': {'C': 1.0}, 'C': {}}
print(dijkstra(graph, 'A')[0])