最短路徑程式碼

最短路徑問題是一個經典的圖論問題，它涉及到找到兩個頂點之間的圖中的最短路徑。最短路徑問題有多種變體，包括單源最短路徑問題（SSSP）和多源最短路徑問題。

在這裡，我將提供一個簡單的程式碼範例，它使用遞迴來解決單源最短路徑問題。這個程式碼使用了一個簡單的圖的表示，其中圖的頂點被編號為0到n-1，並且邊的權重是非負整數。

以下是一個使用Python編寫的簡單遞迴程式碼範例，它解決了單源最短路徑問題：

def shortest_path(graph, source, destination):
    if source == destination:
        return 0
    elif source not in graph:
        return float('inf')
    else:
        weight = graph[source].get(destination, float('inf'))
        for neighbor in graph[source]:
            if neighbor != destination:
                weight = min(weight, graph[source][neighbor] + shortest_path(graph, neighbor, destination))
        return weight

# Example graph
graph = {
    0: {
        1: 6,
        2: 2,
        3: 1
    },
    1: {
        2: 3,
        3: 4
    },
    2: {
        3: 1
    },
    3: {
        4: 2
    }
}

# Example usage
print(shortest_path(graph, 0, 4))

這個程式碼使用了一個字典來表示圖，其中字典的鍵是頂點，值是到其他頂點的邊的映射。每個邊的權重被儲存在一個從頂點到頂點的字典中。

shortest_path 函數接受一個圖、一個源頂點和一個目的地頂點作為輸入。如果源頂點和目的地頂點相同，則返回0（表示源頂點到源頂點的路徑長度為0）。如果源頂點不在圖中，則返回float('inf')（表示源頂點到目的地頂點的路徑不存在）。否則，它返回從源頂點到目的地頂點的最短路徑長度。

這個程式碼使用了一個遞迴的策略來找到最短路徑。對於每個頂點，它會檢查到所有鄰居的邊的權重，並找到到每個鄰居的最短路徑。然後，它會將這些路徑長度與直接邊的權重進行比較，並選擇最小的作為新的最短路徑長度。

請注意，這個程式碼範例只適用於小型的圖，因為它使用的是一個遞迴的解決方案，這可能會導致遞歸深度過深，從而導致堆疊溢出錯誤。對於更大的圖，可以使用貪婪算法（如Dijkstra算法）或動態規劃算法（如Bellman-Ford算法）來解決單源最短路徑問題。