逐次逼近法求最短路

逐次逼近法是一種用於求解最短路徑問題的算法，也被稱為Dijkstra算法。該算法的基本思想是每次從待搜尋的節點集合中選取一個權值最小的節點作為下一步的起始節點，通過不斷逼近最終找到最短路徑。

具體步驟如下：

1. 初始化：將源節點標記為已訪問，並將源節點加入到待搜尋節點集合中。
2. 從待搜尋節點集合中選取一個權值最小的節點，將其標記為已訪問，並將其相鄰的節點也標記為已訪問。
3. 重複執行步驟2，直到待搜尋節點集合為空。
4. 記錄所有已訪問節點的最短路徑值和路徑。

該算法的時間複雜度為O(V^2)，其中V是圖中節點的數量。逐次逼近法適用於稀疏圖的最短路徑求解，因為它能夠避免對所有節點進行深度優先搜尋，從而減少了計算量。

下面是一個使用Python實現的Dijkstra算法示例：

import sys
import heapq

def shortest_path(graph, start):
    # 初始化距離字典和佇列
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    # 逐次逼近求解最短路徑
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    # 返回最短路徑和路徑字典
    return distances, {}

其中，graph是一個字典，表示圖的鄰接表，鍵為節點，值為另一個字典，表示該節點的鄰居及其對應的權值。start是源節點的標識符。distances字典用於記錄每個節點的最短距離，queue佇列用於存儲待處理的節點及其對應的距離。每次從佇列中取出一個距離最小的節點，遍歷其相鄰節點，更新其最短距離和相應的路徑字典。最後返回最短距離和路徑字典。