最短路徑dijkstra算法

Dijkstra算法是一種用於尋找圖中兩點之間最短路徑的算法。以下是算法的基本步驟：

1. 初始化：首先，將所有源節點（起始節點）的距離設定為0，並將所有其他節點的距離設定為無窮大。
2. 標記起始節點：將起始節點的距離標記為已處理。
3. 查找鄰居節點：對於每個未處理的節點，檢查其所有未處理的鄰居節點。如果通過該節點到達鄰居節點的距離小於已知的最短距離，那麼更新這個距離。
4. 更新距離：在每次更新距離時，都會選擇一個最短的路徑。這通常意味著需要訪問一些未處理的鄰居節點。
5. 重複步驟3和4：直到所有節點都被處理過。

以下是一個使用Python實現的簡單例子：

import sys
import heapq

def dijkstra(graph, start):
    distance = {node: float('infinity') for node in graph}
    distance[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distance[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance_to_neighbor = current_distance + weight
            if distance_to_neighbor < distance[neighbor]:
                distance[neighbor] = distance_to_neighbor
                heapq.heappush(queue, (distance_to_neighbor, neighbor))
    return distance

在這個例子中，graph是一個字典，其中鍵是節點，值是另一個字典，表示到該節點的最短路徑的權重。例如，graph = {'A': {'B': 1, 'C': 3}, 'B': {'A': 1, 'C': 2}, 'C': {'A': 3, 'B': 2}}表示從A到B的最短路徑是1，從A到C的最短路徑是3，從B到A的最短路徑也是1等等。

注意，Dijkstra算法適用於沒有負權重的圖。如果圖中存在負權重，可能需要使用其他算法，如Bellman-Ford算法。