離散數學›Ch8 圖形演算法與傳輸網路第 1 題/共 3 題
1. 最短路徑、鄰接矩陣、加權圖
#LS-08-001易最短路徑鄰接矩陣加權圖
- (d) (2 points) Please answer TRUE or FALSE and give a CONCISE explanation: There are exactly 2 shortest paths between and in the graph represented by the adjacency matrix
with , , , , , , .
參考答案與解析
沿用同一張圖(由關聯矩陣還原,見上題)與邊長:、、、、、、。
窮舉 到 的所有簡單路徑與其總長:
- (直接邊 ):長度
- ():長度
- ():長度
- ():長度
前三條路徑長度並列最短,皆為 ;第四條路徑長度為 ,不是最短路徑。
因此 到 之間的最短路徑長度為 ,且共有 3 條不同的最短路徑,而非題目所述的 2 條。故此敘述錯誤(FALSE)。
📄 交大110
▤完整推導請見《WH 資工筆記 · 離散數學》Ch8 圖形演算法與傳輸網路