[Python]Dijkstra 演算法實作

螃蟹_crab

發佈於AI深度學習筆記

2024/12/01 更新2024/12/01 發佈閱讀 10 分鐘

Dijkstra 演算法實作

Dijkstra 是用來找到從一個起點到其他所有點的最短路徑的演算法，適合靜態地圖。

實作步驟

定義地圖：使用圖（Graph）表示地圖。
初始化距離：起點距離設為 0，其餘點設為無限大。
遍歷節點：逐步找出距離最短的節點，更新相鄰節點的距離。
結束條件：所有節點被訪問完成。

程式碼

import heapq  # 引入 heapq 模組，實現最小堆優先隊列

def dijkstra(graph, start):
    # 初始化最短距離字典，將所有節點的最短距離設為無窮大
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 起點到自己的距離為 0
    
    # 儲存已訪問的節點集合，避免重複處理節點
    visited = set()
    
    # 初始化優先隊列，將起點節點及其距離 0 加入隊列
    priority_queue = [(0, start)]  # 優先隊列中的元素是 (距離, 節點)
    
    while priority_queue:
        # 從優先隊列中取出距離最小的節點
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # 如果當前節點已經訪問過，跳過該節點
        if current_node in visited:
            continue
        
        # 將當前節點標記為已訪問
        visited.add(current_node)
        
        # 遍歷當前節點的所有鄰居
        for neighbor, weight in graph[current_node].items():
            # 計算從起點到鄰居的距離
            distance = current_distance + weight
            # 如果新計算出的距離比已知距離更短，則更新最短距離
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 將鄰居節點和其新的距離加入優先隊列
                heapq.heappush(priority_queue, (distance, neighbor))
    
    # 返回從起點到所有節點的最短距離
    return distances

# 測試圖：節點間的連接與對應的邊的權重
graph = {
    'A': {'B': 1, 'C': 4},  # 節點 A 與 B 的距離為 1，A 與 C 的距離為 4
    'B': {'A': 1, 'C': 2, 'D': 5},  # 節點 B 與 A 的距離為 1，B 與 C 的距離為 2，B 與 D 的距離為 5
    'C': {'A': 4, 'B': 2, 'D': 1},  # 節點 C 與 A 的距離為 4，C 與 B 的距離為 2，C 與 D 的距離為 1
    'D': {'B': 5, 'C': 1}  # 節點 D 與 B 的距離為 5，D 與 C 的距離為 1
}

start_node = 'A'  # 設定起點為節點 A
# 呼叫 dijkstra 函數，計算從節點 A 出發的最短距離
shortest_distances = dijkstra(graph, start_node)

# 輸出結果，顯示從節點 A 到其他節點的最短距離
print("Shortest distances from node A:", shortest_distances)

測試輸出

對於這個測試例子，演算法會計算並返回從節點 A 到其他節點的最短距離，輸出結果應該如下：

Shortest distances from node A: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

這表示：

從 A 到 A 的距離是 0。
從 A 到 B 的最短距離是 1。
從 A 到 C 的最短距離是 3。
從 A 到 D 的最短距離是 4。

程式碼詳細解說

1. 引入 `heapq` 模組

import heapq

heapq 是 Python 的標準庫，用於實現最小堆（min-heap）。在 Dijkstra 演算法中，我們使用最小堆來高效地選擇當前距離最小的節點。

2. 定義 `dijkstra` 函數

def dijkstra(graph, start):

這個函數接受兩個參數：

graph：一個字典表示圖，節點作為鍵，與該節點相連的鄰居節點及其邊的權重作為值。
start：起點節點，演算法從這個節點開始計算最短距離。

3. 初始化最短距離字典

distances = {node: float('inf') for node in graph}
distances[start] = 0  # 起點距離為 0

我們使用 distances 字典來存儲每個節點到起點的最短距離。初始時，所有節點的距離設定為無窮大（float('inf')），表示尚未被訪問過。
然後，將起點的距離設置為 0，因為起點到自身的距離是 0。

4. 初始化已訪問節點集合

visited = set()

visited 集合用來存儲已經訪問過的節點。這樣可以避免再次訪問同一節點。

5. 初始化優先隊列

priority_queue = [(0, start)]  # (距離, 節點)

priority_queue 是一個優先隊列，用來存儲尚未訪問的節點，並且根據距離進行排序（最小堆）。初始時，我們將起點節點和其距離（0）加入隊列。

6. 主迴圈

while priority_queue:
    current_distance, current_node = heapq.heappop(priority_queue)

這是 Dijkstra 演算法的核心部分：

當優先隊列不為空時，不斷循環。
我們使用 heapq.heappop(priority_queue) 來取出當前距離最小的節點。這會返回一個二元組 (distance, node)，即節點的距離和節點本身。

7. 如果節點已訪問過，跳過

if current_node in visited:
    continue

如果當前節點已經在 visited 集合中，說明它已經被處理過，這時就跳過它，繼續處理下一個節點。

8. 標記節點為已訪問

visited.add(current_node)

將當前節點標記為已訪問，這樣就不會再次處理它。

9. 更新鄰居節點的距離

for neighbor, weight in graph[current_node].items():
    distance = current_distance + weight
    if distance < distances[neighbor]:
        distances[neighbor] = distance
        heapq.heappush(priority_queue, (distance, neighbor))

對於當前節點的每一個鄰居：

graph[current_node].items() 返回當前節點的所有鄰居及其邊的權重。
計算從起點到鄰居的距離：distance = current_distance + weight。
如果計算出的距離比鄰居當前的距離短，則更新鄰居的最短距離，並將這個鄰居節點及其新的距離加入優先隊列。

10. 返回最短距離字典

return distances

當所有節點都處理完後，返回 distances 字典，其中包含了從起點到每個節點的最短距離。

11. 測試地圖與呼叫函數

# 節點間的連接與距離
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print("Shortest distances from node A:", shortest_distances)