最短路徑範例

最短路徑問題（Shortest Path Problem）是圖論中的一個重要問題，它涉及到在一個圖中找到兩個頂點之間的距離最短的路徑。這裡有一個簡單的範例，我們將使用一個有向圖（Directed Graph）來展示如何找到兩個頂點之間的最短路徑。

假設我們有一個有向圖，它的頂點和邊的權重（weight）如下圖所示：

頂點: A B C D E F
-------------------
A - 1 - B
A - 2 - C
B - 2 - C
B - 3 - D
C - 1 - D
C - 2 - E
D - 1 - E
D - 2 - F
E - 3 - F

我們想要找到從頂點A到頂點F的最短路徑。

為了找到最短路徑，我們可以使用迪傑斯特拉算法（Dijkstra's algorithm），這是一個用來解決單源最短路徑問題的算法。以下是用Python編寫的Dijkstra算法的簡化版本：

from collections import deque

def dijkstra(graph, start):
    distances = {v: float('inf') for v in graph}
    distances[start] = 0

    queue = deque([start])

    while queue:
        u = queue.popleft()
        for v, weight in graph[u].items():
            if distances[v] > distances[u] + weight:
                distances[v] = distances[u] + weight
                queue.append(v)
    return distances

# 假設graph是圖的頂點和邊的映射
graph = {
    'A': {'B': 1, 'C': 2},
    'B': {'C': 2, 'D': 3},
    'C': {'D': 1, 'E': 2},
    'D': {'E': 1, 'F': 2},
    'E': {'F': 3}
}

shortest_distances = dijkstra(graph, 'A')
print(shortest_distances)

執行這個程式，我們會得到從頂點A到其他每個頂點的最短路徑距離。為了找到從A到F的最短路徑，我們只需要查看shortest_distances映射中的F的值。

這個例子中的最短路徑是：A -> B -> C -> D -> F，其總距離為1 + 2 + 1 + 2 = 6。