从深圳到西安，最优运输路径怎么走？——用 Dijkstra 算法搞定它！

总代价 = 时间 × w1 + 费用 × w2

city_graph = {
    '深圳': {'广州': {'time': 1.5, 'cost': 50}, '东莞': {'time': 1.0, 'cost': 30}},
    '广州': {'深圳': {'time': 1.5, 'cost': 50}, '韶关': {'time': 2.5, 'cost': 70}, '长沙': {'time': 5.5, 'cost': 180}},
    '东莞': {'深圳': {'time': 1.0, 'cost': 30}, '惠州': {'time': 1.2, 'cost': 35}},
    '惠州': {'东莞': {'time': 1.2, 'cost': 35}, '武汉': {'time': 8.0, 'cost': 300}},
    '韶关': {'广州': {'time': 2.5, 'cost': 70}, '长沙': {'time': 4.0, 'cost': 120}},
    '长沙': {'韶关': {'time': 4.0, 'cost': 120}, '武汉': {'time': 3.0, 'cost': 100}, '郑州': {'time': 8.0, 'cost': 200}},
    '武汉': {'惠州': {'time': 8.0, 'cost': 300}, '长沙': {'time': 3.0, 'cost': 100}, '郑州': {'time': 4.5, 'cost': 150}, '西安': {'time': 10.0, 'cost': 320}},
    '郑州': {'长沙': {'time': 8.0, 'cost': 200}, '武汉': {'time': 4.5, 'cost': 150}, '洛阳': {'time': 2.0, 'cost': 60}},
    '洛阳': {'郑州': {'time': 2.0, 'cost': 60}, '西安': {'time': 5.0, 'cost': 150}},
    '西安': {'武汉': {'time': 10.0, 'cost': 320}, '洛阳': {'time': 5.0, 'cost': 150}}
}

import heapq
import networkx as nx
import matplotlib.pyplot as plt

def dijkstra(city_graph, start, end, w_time=1.0, w_cost=0.0, broken_edges=None):
    queue = [(0, start, [], 0, 0)]  # (总代价, 当前城市, 路径, 总时间, 总费用)
    visited = set()

    while queue:
        total_weight, city, path, total_time, total_cost = heapq.heappop(queue)
        if city in visited:
            continue
        visited.add(city)
        path = path + [city]
        if city == end:
            return path, total_time, total_cost

        for neighbor, data in city_graph.get(city, {}).items():
            if broken_edges and (city, neighbor) in broken_edges or (neighbor, city) in broken_edges:
                continue
            time = data['time']
            cost = data['cost']
            weight = time * w_time + cost * w_cost
            heapq.heappush(queue, (total_weight + weight, neighbor, path, total_time + time, total_cost + cost))
    
    return None, float('inf'), float('inf')

path, total_time, total_cost = dijkstra(city_graph, '深圳', '西安', w_time=1.0, w_cost=0.0)
print("🚀 最优路径:", " -> ".join(path))
print(f"⏱️ 总时间: {total_time:.1f} 小时")
print(f"💰 总费用: ¥{total_cost:.2f}")

🚀 最优路径: 深圳 -> 广州 -> 韶关 -> 长沙 -> 武汉 -> 西安
⏱️ 总时间: 21.0 小时
💰 总费用: ¥770.00

path, total_time, total_cost = dijkstra(city_graph, '深圳', '西安', w_time=1.0, w_cost=0.01)
print("📊 双目标最优路径:", " -> ".join(path))
print(f"⏱️ 总时间: {total_time:.1f} 小时")
print(f"💰 总费用: ¥{total_cost:.2f}")

📊 双目标最优路径: 深圳 -> 东莞 -> 惠州 -> 武汉 -> 西安
⏱️ 总时间: 24.2 小时
💰 总费用: ¥815.00

broken = [('武汉', '西安')]
path, total_time, total_cost = dijkstra(city_graph, '深圳', '西安', broken_edges=broken)
print("🛑 路线断联后的路径:", " -> ".join(path))
print(f"⏱️ 总时间: {total_time:.1f} 小时")
print(f"💰 总费用: ¥{total_cost:.2f}")

🛑 路线断联后的路径: 深圳 -> 广州 -> 韶关 -> 长沙 -> 武汉 -> 郑州 -> 洛阳 -> 西安
⏱️ 总时间: 25.5 小时
💰 总费用: ¥950.00

def visualize_path(city_graph, path):
    G = nx.Graph()
    for city, neighbors in city_graph.items():
        for neighbor, data in neighbors.items():
            G.add_edge(city, neighbor, weight=data['time'])

    pos = nx.spring_layout(G, seed=42)
    plt.figure(figsize=(12, 8))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=2000, font_size=10)
    edge_labels = {(u, v): f"{d['weight']}h" for u, v, d in G.edges(data=True)}
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

    if path:
        edges_in_path = list(zip(path, path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=edges_in_path, width=3, edge_color='red')
        nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='orange')
    plt.title("📍 从深圳到西安的最优运输路径")
    plt.show()

visualize_path(city_graph, path)