1959 - Dijkstra 的最短路徑演算法（演算法設計的典範）#

import heapq

# 1) Dijkstra 演算法（二元堆積實現，O((V+E) log V)）
def dijkstra(graph, start):
    """graph: {node: [(neighbor, weight), ...]}"""
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    visited = set()
    pq = [(0, start)]   # (距離, 節點)
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if d + w < dist[v]:          # 鬆弛
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, prev

def shortest_path(prev, target):
    """回溯最短路徑"""
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]

# 2) 測試：荷蘭城市的地圖（Dijkstra 1956 的原始問題）
graph = {
    '阿姆斯特丹': [('烏特勒支', 4), ('海牙', 6)],
    '烏特勒支':  [('阿姆斯特丹', 4), ('鹿特丹', 3), ('恩荷芬', 8)],
    '海牙':      [('阿姆斯特丹', 6), ('鹿特丹', 2)],
    '鹿特丹':    [('烏特勒支', 3), ('海牙', 2), ('恩荷芬', 5)],
    '恩荷芬':    [('烏特勒支', 8), ('鹿特丹', 5)],
}

print("Dijkstra 最短路徑（荷蘭城市）：")
dist, prev = dijkstra(graph, '阿姆斯特丹')
for city in ['海牙', '鹿特丹', '恩荷芬', '烏特勒支']:
    path = shortest_path(prev, city)
    print(f"  阿姆斯特丹 → {city}: 距離 = {dist[city]}, 路徑 = {' → '.join(path)}")

# 3) 複雜度驗證：邊的鬆弛次數
print("\n鬆弛操作的次數（O(E + V log V) 的驗證）：")
n_relax = 0
def dijkstra_count(graph, start):
    global n_relax
    n_relax = 0
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    visited = set()
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited: continue
        visited.add(u)
        for v, w in graph[u]:
            n_relax += 1
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

E = sum(len(adj) for adj in graph.values())
V = len(graph)
dijkstra_count(graph, '阿姆斯特丹')
print(f"  V = {V}, E = {E}")
print(f"  鬆弛次數 = {n_relax}（≤ E = {E}）")
print("  → 鬆弛次數 = O(E)，堆積操作 = O(V log V)")

# 4) A* 演算法：加入啟發式（Dijkstra 1968 的改進）
print("\nA* 演算法（Dijkstra + 啟發式）：")
def astar(graph, start, goal, h):
    """h: 啟發式函數（如直線距離）"""
    dist = {start: 0}
    prev = {start: None}
    pq = [(h(start, goal), 0, start)]   # (f = g + h, g, 節點)
    visited = set()
    explored = 0
    while pq:
        f, g, u = heapq.heappop(pq)
        if u in visited: continue
        visited.add(u)
        explored += 1
        if u == goal:
            return dist[goal], prev, explored
        for v, w in graph[u]:
            if g + w < dist.get(v, float('inf')):
                dist[v] = g + w
                prev[v] = u
                heapq.heappush(pq, (g + w + h(v, goal), g + w, v))
    return None, prev, explored

# 啟發式：城市間的「座標距離」（簡化用字母序距離）
coords = {'阿姆斯特丹': (0, 0), '烏特勒支': (4, 0), '海牙': (0, 6),
          '鹿特丹': (3, 6), '恩荷芬': (8, 2)}
def h(a, b):
    (x1,y1), (x2,y2) = coords[a], coords[b]
    return ((x1-x2)**2 + (y1-y2)**2)**0.5

d, prev, explored = astar(graph, '阿姆斯特丹', '恩荷芬', h)
path = shortest_path(prev, '恩荷芬')
print(f"  阿姆斯特丹 → 恩荷芬: 距離 = {d}, 路徑 = {' → '.join(path)}")
print(f"  A* 探索了 {explored} 個節點")
d2, _ = dijkstra(graph, '阿姆斯特丹')
print(f"  Dijkstra 需探索全部 {len(graph)} 個節點")
print("  → A* 只探索「有希望」的路徑（啟發式的威力）")

Dijkstra 最短路徑（荷蘭城市）：
  阿姆斯特丹 → 海牙: 距離 = 6, 路徑 = 阿姆斯特丹 → 海牙
  阿姆斯特丹 → 鹿特丹: 距離 = 7, 路徑 = 阿姆斯特丹 → 烏特勒支 → 鹿特丹
  阿姆斯特丹 → 恩荷芬: 距離 = 12, 路徑 = 阿姆斯特丹 → 烏特勒支 → 恩荷芬
  阿姆斯特丹 → 烏特勒支: 距離 = 4, 路徑 = 阿姆斯特丹 → 烏特勒支

鬆弛操作的次數（O(E + V log V) 的驗證）：
  V = 5, E = 12
  鬆弛次數 = 12（≤ E = 12）
  → 鬆弛次數 = O(E)，堆積操作 = O(V log V)

A* 演算法（Dijkstra + 啟發式）：
  阿姆斯特丹 → 恩荷芬: 距離 = 12, 路徑 = 阿姆斯特丹 → 烏特勒支 → 恩荷芬
  A* 探索了 3 個節點
  Dijkstra 需探索全部 5 個節點
  → A* 只探索「有希望」的路徑（啟發式的威力）