Deadline : 1/21/2018 23:59 "Read before submission"
包含求解下列三個問題:
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
1.Generate a graph g in random,the density and directivity of graph can be assigned by user.
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.
2.Find transitive closure of directed graph.
Print adjacency matrix (Sparse graph)
Print adjacency matrix (Complete graph)
The process of solving single source all destinations
Dijkstra algorithm
Use 'from' array to trace shortest path
Result of all pair shortest path
Result of transitive closure