萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網頁製作 >> HTML 腳本教學

Python 實現 Dijkstra 最短路徑算法:鄰接矩陣與路徑重構完整代碼

問題建模:帶權無向圖

# 節點索引映射
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
copyright © 萬盛學電腦網 all rights reserved