Dijkstra 演算法例 II

Dijkstra 範例 II

---

圖表描述

假設圖如下：

    (A)---2--->(B)
     |         / |
     5        1  |
     |       /   |
    (C)<---4----(D)

鄰接表表示

graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'D': 1},
    'C': {},
    'D': {'C': 4}
}

---

簡化版 Dijkstra 演算法

def dijkstra(graph, start):
    # 初始化最短距離
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 起點距離為 0
    visited = set()  # 已訪問節點

    while len(visited) < len(graph):
        # 找出目前距離最短且未訪問的節點
        current_node = None
        for node in distances:
            if node not in visited and (current_node is None or distances[node] < distances[current_node]):
                current_node = node

        # 訪問該節點
        visited.add(current_node)

        # 更新鄰居距離
        for neighbor, weight in graph[current_node].items():
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance

    return distances

# 測試圖
graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'D': 1},
    'C': {},
    'D': {'C': 4}
}

# 執行 Dijkstra 演算法
result = dijkstra(graph, 'A')

# 輸出結果
print("從節點 A 到其他節點的最短距離：")
for node, distance in result.items():
    print(f"到 {node} 的最短距離為 {distance}")

---

重點

1. 去掉路徑追踪：

   • 只關注最短距離的計算，避免多餘的路徑儲存。

2. 優化結構：

   • 使用字典操作取代優先佇列

3. 步驟：

   • 初始化所有節點距離為無窮大。
   • 每次選取距離最短的未訪問節點。
   • 更新其鄰居的距離。

---

執行結果

從節點 A 到其他節點的最短距離：
到 A 的最短距離為 0
到 B 的最短距離為 2
到 C 的最短距離為 6
到 D 的最短距離為 3