最短路徑程式

最短路徑問題是一個經典的圖論問題，它旨在找到兩個節點之間或一組節點之間的最短路徑。最短路徑算法有很多種，以下是一些常用的算法：

1. 迪傑斯特拉（Dijkstra）算法：用於找到從一個給定源節點到圖中其他所有節點的最短路徑。它適用於權重為非負數的圖。

2. 弗洛伊德-沃特森（Floyd-Warshall）算法：用於找到圖中的所有頂點對之間的最短路徑。它適用於權重為任意值的圖，包括負權重。

3. 貝爾曼-福特（Bellman-Ford）算法：用於找到有負權重邊的圖中的最短路徑。

4. 約翰森（Johnson）算法：用於找到帶負權重邊的圖中的所有頂點對之間的最短路徑。

5. A*算法：是一種啟發式搜尋算法，用於尋找最短路徑。它結合了貪婪算法和啟發式函式來指導搜尋過程。

這些算法的實現通常需要使用數據結構，如優先佇列或堆疊來高效地存儲和處理節點和邊。

下面是一個簡單的Dijkstra算法的Python實現，用於找到從一個給定的源節點到圖中其他節點的最短路徑：

from collections import deque

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 dijkstra(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0
        q = deque()
        q.append(src)
        while q:
            u = q.popleft()
            for v, w in self.graph[u]:
                if dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w
                    q.append(v)

        return dist

# 示例
g = Graph(5)
g.addEdge(0, 1, 4)
g.addEdge(0, 2, 5)
g.addEdge(0, 3, 1)
g.addEdge(1, 2, 2)
g.addEdge(2, 3, 6)
g.addEdge(2, 4, 8)
g.addEdge(3, 4, 7)

dist = g.dijkstra(0)
print(dist)

這個例子中，我們創建了一個有5個頂點的圖，並添加了一些邊。然後我們調用dijkstra方法來找到從頂點0到其他所有頂點的最短路徑。dijkstra方法返回一個數組，其中每個元素是頂點到頂點0的最短路徑的距離。

請注意，這個實現假設圖是無向的，並且邊的權重是非負的。如果你需要處理有向圖或有負權重邊的圖，你可能需要使用不同的算法或對上面的代碼進行修改。