最短路徑
學習資源
優缺點
| 演算法名稱 | 優點 | 缺點 | 解釋 | 程式碼 |
|---|---|---|---|---|
| Floyd-Warshall 演算法 | 適用於有向圖或無向圖，處理帶有負權重的圖 | 時間複雜度高，適用於小型圖 | 用於找解決所有點對之間的最短路徑 | Floyd-Warshall 程式碼範例 |
| Union-find Algorithm (並查集) | 查詢和合併的時間複雜度都很快 | 不適用於帶權重的邊，只能處理無權重的圖 | 用於快速查詢兩個點是否屬於同一集合 | 並查集 (Union-Find) 程式碼範例 |
| Dijkstra 演算法 | 適用於有向圖和無向圖，處理非負權重的圖 | 無法處理帶有負權重的邊 | 用於找解決一個點到其他所有點的最短路徑 | Dijkstra 程式碼範例 |
| Bellman-Ford 演算法 | 可處理帶有負權重的圖 | 時間複雜度較高，對於大型圖效能較差 | 用於找解決一個點到其他所有點的最短路徑，且可處理帶有負權重的邊 | Bellman-Ford 程式碼範例 |
| Bellman-Ford 演算法 - 佇列優化 | 在處理稠密圖時效能較佳 | 實現較複雜，不如 Dijkstra 演算法常用 | Bellman-Ford 演算法的佇列優化版本 | 同上 |
程式碼範例
python
def find(root, x):
if root[x] != x:
root[x] = find(root, root[x])
return root[x]
def union(root, rank, x, y):
root_x = find(root, x)
root_y = find(root, y)
if root_x != root_y:
if rank[root_x] > rank[root_y]:
root_y, root_x = root_x, root_y
elif rank[root_x] == rank[root_y]:
rank[root_y] += 1
root[root_y] = root_x
# Example usage:
n = 5
parent = list(range(n))
rank = [0] * n
# Perform union operations
union(parent, rank, 0, 1)
union(parent, rank, 2, 3)
union(parent, rank, 0, 4)
# Check if elements are in the same set
print(find(parent, 1) == find(parent, 4)) # True
print(find(parent, 2) == find(parent, 3)) # False其實也可以拿來解生成樹
牛刀小試
Contributors
lucashsu95