说明

代码

import heapq

def bellman_ford(graph, start):
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight

    return distance

def dijkstra(graph, start):
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distance[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance_via_current = current_distance + weight
            if distance_via_current < distance[neighbor]:
                distance[neighbor] = distance_via_current
                heapq.heappush(priority_queue, (distance[neighbor], neighbor))

    return distance

def johnson(graph):
    # Step 1: Add a new source vertex
    new_source = 'new_source'
    graph[new_source] = {v: 0 for v in graph}

    # Step 2: Run Bellman-Ford from the new source
    potential = bellman_ford(graph, new_source)

    # Step 3: Reweight the edges
    reweighted_graph = {}
    for u in graph:
        reweighted_graph[u] = {}
        for v, weight in graph[u].items():
            reweighted_graph[u][v] = weight + potential[u] - potential[v]

    # Step 4: Run Dijkstra for each vertex
    all_pairs_shortest_paths = {}
    for vertex in graph:
        all_pairs_shortest_paths[vertex] = dijkstra(reweighted_graph, vertex)

    return all_pairs_shortest_paths

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1},
    'D': {}
}

shortest_paths = johnson(graph)
print(shortest_paths)