最短路徑范例

最短路徑問題是一個經典的圖論問題，它涉及到找到從一個給定的起始節點到目標節點的最短路徑。這個問題有許多不同的變體和算法來解決它，下面是一個簡單的示例，展示了如何找到一個圖的最短路徑。

假設我們有一個簡單的圖，它代表了一個城市中的街道網路，如圖所示：

  A --+-- B --+-- C
      |     |     |
      D --+-- E --+-- F

我們想要找到從A到F的最短路徑。最短路徑算法會遍歷圖中的所有邊，計算出從起始節點到目標節點的所有可能路徑的長度，並選擇最短的一個。

在這個例子中，從A到F的最短路徑是 A -> B -> E -> F，總長度為2 + 2 + 2 = 6。

下面是一個簡單的Python程式，它使用廣度優先搜尋（BFS）來找到最短路徑：

import queue

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 頂點數
        self.graph = [[] for _ in range(vertices)]

    def addEdge(self, u, v, w):
        self.graph[u].append((v, w))

    def BFS(self, src, dest):
        queue = queue.Queue()
        dist = [float('inf')] * self.V
        dist[src] = 0
        queue.put(src)
        while not queue.empty():
            cur = queue.get()
            for i in range(len(self.graph[cur])):
                adj, weight = self.graph[cur][i]
                if dist[adj] > dist[cur] + weight:
                    dist[adj] = dist[cur] + weight
                    queue.put(adj)
        print(dist)
        return dist[dest] if dist[dest] != float('inf') else -1

# 創建圖
g = Graph(6)
g.addEdge(0, 1, 1)
g.addEdge(0, 2, 2)
g.addEdge(1, 3, 2)
g.addEdge(1, 4, 1)
g.addEdge(2, 3, 1)
g.addEdge(2, 5, 2)
g.addEdge(3, 5, 1)

# 找到最短路徑
print(g.BFS(0, 5))

這個程式定義了一個圖類，它有一個鄰接列表表示圖的結構。然後，它使用廣度優先搜尋來找到從0（A）到5（F）的最短路徑。程式的輸出應該是6，這是A到F的最短路徑長度。