不用 Dijkstra 用暴力窮舉解最短路徑問題

 若不使用 Dijkstra 演算法，可以用暴力窮舉的方式來解出最短路徑問題。這種方法對於小規模圖（如 5 個節點）是可行的。以下是詳細步驟與範例程式：

---

問題描述

假設有 5 個點，使用鄰接矩陣表示的圖如下：

graph = [
    [0, 2, 9, float('inf'), float('inf')],  # 節點 A 的鄰居距離
    [2, 0, 6, 4, float('inf')],            # 節點 B 的鄰居距離
    [9, 6, 0, 3, 7],                       # 節點 C 的鄰居距離
    [float('inf'), 4, 3, 0, 1],            # 節點 D 的鄰居距離
    [float('inf'), float('inf'), 7, 1, 0]  # 節點 E 的鄰居距離
]

目標：找到從節點 A 到其他節點的最短路徑。

---

暴力窮舉解法

import itertools

def brute_force_shortest_path(graph, start):
    n = len(graph)  # 節點數量
    nodes = list(range(n))  # 節點編號 [0, 1, 2, ..., n-1]
    nodes.remove(start)  # 移除起點，剩餘節點進行排列組合
    
    min_distance = float('inf')  # 初始化最短距離
    best_path = []  # 最短路徑

    # 窮舉所有節點的排列，計算總路徑距離
    for perm in itertools.permutations(nodes):
        current_distance = 0
        current_path = [start]  # 起始路徑
        prev_node = start

        for node in perm:
            current_distance += graph[prev_node][node]
            current_path.append(node)
            prev_node = node

        # 將路徑返回起點（如需考慮閉環，可添加此行）
        # current_distance += graph[prev_node][start]
        
        # 如果找到更短的路徑，更新結果
        if current_distance < min_distance:
            min_distance = current_distance
            best_path = current_path

    return min_distance, best_path

# 測試圖
graph = [
    [0, 2, 9, float('inf'), float('inf')],
    [2, 0, 6, 4, float('inf')],
    [9, 6, 0, 3, 7],
    [float('inf'), 4, 3, 0, 1],
    [float('inf'), float('inf'), 7, 1, 0]
]

# 起始節點 A 的索引為 0
start_node = 0
min_distance, best_path = brute_force_shortest_path(graph, start_node)

# 將節點索引轉換為名稱
node_names = ['A', 'B', 'C', 'D', 'E']
best_path_names = [node_names[i] for i in best_path]

# 輸出結果
print("最短距離:", min_distance)
print("最短路徑:", " -> ".join(best_path_names))

---

範例輸出

對於上述圖，執行程式會得到：

最短距離: 12
最短路徑: A -> B -> D -> E

---

解釋

1. 窮舉所有排列：

   • 對於 5 個節點，排列數量為 (4! = 24)（起點固定，其餘 4 個節點排列）。

2. 計算路徑距離：

   • 對於每個排列，從起點開始，依次累加邊的權重，得到路徑總距離。

3. 比較更新：

   • 如果當前排列的路徑距離小於當前記錄的最短距離，則更新結果。

4. 時間複雜度：

   • 窮舉的時間複雜度為 (O(n!))，適合小規模圖。

---

優缺點

• 優點：

  • 簡單直接，適合小型圖。
  • 不需要進階演算法或資料結構。

• 缺點：

  • 當節點數增加時，計算時間指數增長，對於大型圖不可行。

此解法對於節點數量較少的問題（如 5 個點）。