Bonus Shortest Path

包含求解下列三個問題：

1. 單一起點到所有目的地之最短路徑

2. 任意兩點間的最短路徑

3. 計算出遞移封閉

This bonus assignment contains three problems

1.single source all destinations

2.all pairs shortest paths

3.transitive closure

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

輸出： 最短距離 shortest paths

Requirement

1.Generate a graph g in random,the density and directivity of graph can be assigned by user.

For Problem 1 and 2 :

2. Find shortest distance from single source to every vertices (single source all destinations)

3.Find shortest distance between and two points (all pairs shortest paths)

4.User can trace the process of solving this problem.

For Problem 3:

2.Find transitive closure of directed graph.

Program Example

Reference

https://sites.google.com/site/sjdsifm/ProgrammingAssignment/09-shortest-paths-ssad-all-pairs-transitive-closure