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

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 的求算過程]

[all pairs shortest paths 的結果]

[ transtive closure 的結果 ]

繳交期限:

甲班：2013/05/27 23:00 ,

乙班：2013/05/28 23:00 ,

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