最短路徑動態規劃

最短路徑問題是圖論中的一個基本問題，它的目標是在給定的圖中找到兩個頂點之間的最低成本路徑。動態規劃是一種解決最優化問題的方法，它通過分治策略來降低問題的複雜度。在解決最短路徑問題時，動態規劃可以幫助我們高效地找到從一個頂點到另一個頂點的最短路徑。

最短路徑問題的動態規劃解決方案通常基於Bellman-Ford算法或Dijkstra算法。這些算法通過在圖中逐步擴展最短路徑來工作。在每一輪擴展中，它們都會更新已經找到的最短路徑的頂點的鄰居的最短路徑估計。這種方法可以有效地找到從一個源頂點到所有其他頂點的最短路徑。

以下是一個簡單的動態規劃算法來解決最短路徑問題的示例：

def shortest_path(graph, source):
    # 初始化最短路徑距離為無窮大
    dist = {v: float('inf') for v in graph}

    # 源頂點的最短路徑距離為0
    dist[source] = 0

    # 使用動態規劃來逐步更新最短路徑
    for i in range(len(graph)):
        for v in graph:
            for w in graph[v]:
                if dist[v] != float('inf') and dist[w] > dist[v] + graph[v][w]:
                    dist[w] = dist[v] + graph[v][w]

    # 返回最短路徑距離
    return dist

# 示例圖形
graph = {
    'A': {'B': 1, 'C': 2, 'D': 3},
    'B': {'A': 1, 'C': 3, 'D': 2},
    'C': {'A': 2, 'B': 3, 'D': 1},
    'D': {'A': 3, 'B': 2, 'C': 1}
}

# 查找從'A'到其他頂點的最短路徑
shortest_paths = shortest_path(graph, 'A')
for v in graph:
    print(f"The shortest path from 'A' to '{v}' is {shortest_paths[v]}")

這個算法會疊代地更新最短路徑距離，直到沒有任何頂點的距離可以進一步減少。這種方法對於有向無環圖（DAG）來說是線性的，對於一般圖則可能是二次的。實際上，Bellman-Ford算法和Dijkstra算法都是基於這種動態規劃的思想來解決最短路徑問題的。