Dijkstra 演算法 III

  Dijkstra 演算法 III

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': 10, 'C': 15,'D':30},

    'B': {'D': 15},

    'C': {'D': 8},

    'D': {}

}

# 執行 Dijkstra 演算法

start_node = 'A'

result = dijkstra(graph, start_node)

# 輸出結果

print("從節點", start_node, "到其他節點的最短距離：")

for node, distance in result.items():

    print(f"到 {node} 的最短距離為 {distance}")

# Output:

# 從節點 A 到其他節點的最短距離：

# 到 A 的最短距離為 0

# 到 B 的最短距離為 10

# 到 C 的最短距離為 15

# 到 D 的最短距離為 23

1. 初始化：

   • 建立一個 distances 字典來記錄從起點到每個節點的最短距離。
   • 初始時，起點的距離為 0，其他所有節點的距離為「無窮大」（float('inf')）。

2. 選擇最近節點：

   • 從所有未訪問的節點中選擇距離起點最近的節點。

3. 更新鄰居的距離：

   • 對於當前節點的每個鄰居，計算新的距離：
     • 新距離 = 當前節點到起點的距離 + 邊的權重。
   • 如果新距離小於當前記錄的距離，則更新。

4. 重複步驟：

   • 重複選擇最近節點並更新鄰居的步驟，直到所有節點都被訪問。

5. 返回結果：

   • 最終，distances 字典記錄了從起點到所有節點的最短距離。

---

範例運算追踪

測試圖

graph = {
    'A': {'B': 10, 'C': 15, 'D': 30},
    'B': {'D': 15},
    'C': {'D': 8},
    'D': {}
}

圖結構：

       10        15
    (A)---(B)--------(D)
     |               /
    15              /
     \             8
      (C)---------

執行步驟

1. 初始化：

   distances = {'A': 0, 'B': inf, 'C': inf, 'D': inf}
   visited = set()
   

2. 第一輪迴圈：

   • 找出最短距離的節點：A，距離為 0。
   • 更新 A 的鄰居：
     • B: 0 + 10 = 10，更新為 10。
     • C: 0 + 15 = 15，更新為 15。
     • D: 0 + 30 = 30，更新為 30。

   distances = {'A': 0, 'B': 10, 'C': 15, 'D': 30}
   visited = {'A'}
   

3. 第二輪迴圈：

   • 找出最短距離的節點：B，距離為 10。
   • 更新 B 的鄰居：
     • D: 10 + 15 = 25，比 30 小，更新為 25。

   distances = {'A': 0, 'B': 10, 'C': 15, 'D': 25}
   visited = {'A', 'B'}
   

4. 第三輪迴圈：

   • 找出最短距離的節點：C，距離為 15。
   • 更新 C 的鄰居：
     • D: 15 + 8 = 23，比 25 小，更新為 23。

   distances = {'A': 0, 'B': 10, 'C': 15, 'D': 23}
   visited = {'A', 'B', 'C'}
   

5. 第四輪迴圈：

   • 找出最短距離的節點：D，距離為 23。
   • 無鄰居需要更新。

   distances = {'A': 0, 'B': 10, 'C': 15, 'D': 23}
   visited = {'A', 'B', 'C', 'D'}
   

6. 結束：

   • 所有節點已訪問，最短距離計算完成。

---

結果輸出

從節點 A 到其他節點的最短距離：
到 A 的最短距離為 0
到 B 的最短距離為 10
到 C 的最短距離為 15
到 D 的最短距離為 23