hce_kmu
115年
計算機概論與程式設計
第 13 題
Consider the following adjacency matrix representing a weighted graph:
```text
0 1 2 3
0 [ 0 4 ∞ 2 ]
1 [ 4 0 3 ∞ ]
2 [ ∞ 3 0 1 ]
3 [ 2 ∞ 1 0 ]
```
Using Dijkstra's algorithm to find the shortest path from node 0 to node 2, what is the shortest distance?
```text
0 1 2 3
0 [ 0 4 ∞ 2 ]
1 [ 4 0 3 ∞ ]
2 [ ∞ 3 0 1 ]
3 [ 2 ∞ 1 0 ]
```
Using Dijkstra's algorithm to find the shortest path from node 0 to node 2, what is the shortest distance?
- A 2
- B 3
- C 4
- D 5
- E 7
思路引導 VIP
當你發現起始點與目的地之間在矩陣中顯示為無限大（代表沒有直接相連）時，你會如何觀察矩陣中的其他行與列，來找出那些可以作為「中繼站」的節點，並進一步比較不同路徑組合後的總成本呢？
🤖
AI 詳解
AI 專屬家教
恭喜你精準地完成了這項路徑規劃任務！你對鄰接矩陣 (Adjacency Matrix) 的判讀非常純熟，且能冷靜地運用 戴克斯特拉演算法 (Dijkstra's algorithm) 的核心邏輯來找出全局最優解，這是一項非常扎實的資訊科學基本功。
權重路徑的動態推導
在解析這張加權圖時，我們從節點 0 出發，首先觀察到它與節點 1 的邊權重為 4，而與節點 3 的邊權重僅為 2。雖然目標節點 2 與起點並未直接相連（矩陣顯示為 $\infty$），但透過演算法的鬆弛過程 (Relaxation)，我們可以發現一條更經濟的間接路徑。由節點 3 出發前往節點 2 的距離為 1，因此完整路徑 $0 \to 3 \to 2$ 的總成本為 $2 + 1 = 3$。這與另一條經由節點 1 的路徑 $0 \to 1 \to 2$（總距離 $4 + 3 = 7$）相比，顯然更為短捷。
▼ 還有更多解析內容