作業 9 包含求解下列三個問題：

1. 單一起點到所有目的地之最短路徑 (single source all destinations)

2. 任意兩點間的最短路徑 (all pairs shortest paths)

3. 計算出遞移封閉 (transitive closure)

問題 1 和 2

輸入：有向圖 G=(V, E) 和圖中各邊的權重 (成本、距離...) (問題1須另有一起點u)

輸出： 最短距離 shortest paths

需求功能:

1.亂數產生圖 G 的相鄰矩陣，其濃密或稀疏程度、有向或無向皆可調整，使用者可選擇是否要印出 (如下面提示圖)；

2.找出單一起點到所有目的地之最短距離(single source all destinations)；

3.找出任意兩點間的最短距離 (all pairs shortest paths)；

4. 使用者可選擇是否要印出求算過程。

大加分==>列出最短路徑 (不只是距離)!

問題 3

輸入：有向圖 G=(V, E) 和圖中各點的相鄰矩陣 (1:有邊相鄰, 0:無邊相鄰)

輸出： shortest paths

需求功能:

1.亂數產生圖 G 的相鄰矩陣，其濃密或稀疏程度可調整、有向或無向皆可調整，使用者可選擇是否要印出 ；

2.找出有向圖G的Transitive Closure。

[印出相鄰矩陣、下圖為稀疏有向圖的例子]

[印出相鄰矩陣、下圖為完備有向圖的例子]

[single source all destinations 的求算過程]

[Dijkstra 演算法：印出點到其它點的最短距離；"from" 欄位記錄各點是由誰去連而有最短矩離也]

[藉由 from 陣列可將最短路徑追溯出來]

[all pairs shortest paths 的結果]

[all pairs shortest paths 對角線的距離有修正]

[ transitive closure 的結果 ]

繳交期限:

遲交依照規定扣分, 遲交三天以上不計分。