作業 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.可用讀檔，讀入現有的相鄰矩陣(提示：參考老鼠走迷宮的讀檔)；

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

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

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

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

問題 3

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

輸出： shortest paths

需求功能:

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

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

Program Example (Generation of a Cost/Weight Matrix )

程式範例

Report the shortest paths for each pair of two vertices (Something is wrong here. Please find it out and figure out what is going on.)

Compute transitive closure using the weight matrix as the 0/1 adjacency matrix

Reduce the density of the edges in G' (which is directed) by proper parameters

The All pairs shortest paths of G' (The connectivity of vertices is sparse.)

The transitive closure of G' 

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

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

[single source all destinations 的求算過程]

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

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

[all pairs shortest paths 的結果]

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

[ transtive closure 的結果 ]

========================================================================

作業繳交規則:https://sites.google.com/site/sjdsalg/homework

繳交的作業檔案 (上傳 moodle) 請務必包含"整個專案檔"(包含程式執行檔)

必須為可獨立執行檔01. 如何製作獨立執行檔

並且請"依照規定的檔案命名方式"命名

繳交期限:依照FB與MOODLE上的公布之繳交日期，如兩者期限不同請聯絡助教

請盡早繳交 , 避免網路壅塞 , 導致無法繳交!

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

============================================================================