問題建模:帶權無向圖
# 節點索引映射
nodes = ['A','B','C','D','E','F','G'] # 0..6
# 邊列表 (u, v, weight)
edges = [
('A','F',9), ('A','B',10), ('A','G',15),
('B','F',2), ('G','F',3), ('G','E',12),
('G','C',10), ('C','E',1), ('E','D',7)
]
# 構建鄰接矩陣
n = len(nodes)
graph = [[0]*n for _ in range(n)]
for u, v, w in edges:
i, j = nodes.index(u), nodes.index(v)
graph[i][j] = graph[j][i] = w
Dijkstra 類實現
class DijkstraPath:
def __init__(self, graph):
self.graph = graph
self.n = len(graph)
def __call__(self, src, dst):
self.src = src
self.dst = dst
return self._dijkstra()
def _dijkstra(self):
dist = [float('inf')] * self.n
prev = [-1] * self.n
visited = [False] * self.n
dist[self.src] = 0
for _ in range(self.n):
# 選擇未訪問的最小距離節點
u = -1
min_d = float('inf')
for i in range(self.n):
if not visited[i] and dist[i] < min_d:
min_d = dist[i]
u = i
if u == -1: break
visited[u] = True
# 鬆弛鄰接邊
for v, w in enumerate(self.graph[u]):
if w > 0 and not visited[v]:
alt = dist[u] + w
if alt < dist[v]:
dist[v] = alt
prev[v] = u
# 重構路徑
path = []
cur = self.dst
while cur != -1:
path.append((nodes[cur], dist[cur]))
cur = prev[cur]
path.reverse()
return path
# 使用
dp = DijkstraPath(graph)
path = dp(nodes.index('A'), nodes.index('D'))
for node, d in path:
print(f"{node} (dist={d})")
# A (0) -> F (9) -> G (12) -> C (22) -> E (23) -> D (30)
關鍵點
- 鄰接矩陣適合稠密圖,稀疏圖改用鄰接表
dict/list 更省空間
- 時間複雜度 O(V²),配合優先隊列(堆)可優化至 O(E log V)
prev 數組記錄前驅節點,逆向回溯得最短路徑
heapq 優化版(大圖推薦)
import heapq
def dijkstra_heap(graph, src, dst):
n = len(graph)
dist = [float('inf')]*n
prev = [-1]*n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
if u == dst: break
for v, w in enumerate(graph[u]):
if w and d + w < dist[v]:
dist[v] = d + w
prev[v] = u
heapq.heappush(pq, (dist[v], v))
# 重構路徑同前
return path