如何從加權圖形中找出最短路徑

從加權圖形中找出最短路徑可以使用多種算法，其中最常用的是迪傑斯特拉（Dijkstra）算法。這個算法可以用來找出兩個點之間的單源最短路徑。

以下是使用Dijkstra算法找出最短路徑的步驟：

1. 初始化源點的距離為0，其他點的距離為無窮大。
2. 從未訪問過的點中選擇距離源點最近的點。
3. 更新與該點相連的未訪問點的距離。
4. 重複步驟2和步驟3，直到所有點都被訪問過或找到目標點為止。

以下是一個簡單的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 shortestPath(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(1, 3, 6)
g.addEdge(2, 3, 3)
g.addEdge(2, 4, 7)
g.addEdge(3, 4, 2)

# 查找從頂點0到其他頂點的最短路徑
dist = g.shortestPath(0)

# 輸出最短路徑
for i in range(1, g.V):
    if dist[i] != float('inf'):
        print(f"Vertex {i} is reachable with distance {dist[i]} from source vertex 0")

這個程式會輸出從頂點0到其他每個頂點的最短路徑距離。請注意，這個算法只適用於非負權重的圖形，並且在圖形中有無限循環時可能會出現問題。