The Shortest Path

The Shortest Path

The Graph is defined by the nodes、the edges and the edge weights. You are asked to complete a program to input a graph、the starting node and the ending node and to output the shortest path cost and its traveling nodes.

Input Format:
First、input graph. The formats as follows:
[GRAPH]
<node A>、<node B>、<edge weight 0>
<node B>、<node C>、<edge weight 1>
…..
[END]

Second、input starting and ending node pair. The formats as follows:
<starting node>、<ending node>

Output Format:
The shortest path cost: <minimum weight>
Traveling nodes: <starting node>、<node 0>、…. 、<ending node>

Sample Input:
The example graph:





[GRAPH]
1、2、2
2、4、3
1、3、1
3、4、2
3、5、3
4、5、2
[END]
2、5

Sample Output:
The shortest path cost: 5
Traveling nodes: 2、4、5

困難度：***
時間複雜度：O(n^2)
程式語言：C++

解題原理：
1. 以字串讀入後進行處理，一次處理一行
2. 建立圖形類別（包含點、邊的關聯）
3. 使用 Dijkstra 演算法找出最短路徑

Dijkstra 演算法：
1. 假設圖形 G 存在點集合 V，每個點有其權重 W，D 為點集合權重之集合
2. 令 Q 為 V 之點集合複本，Pi 為最佳路徑之點集合
3. 當 Q 集合大於零進入步驟 4，否則到步驟 8
4. 從 Q 中取出在 D 中最小的點權重 u，以 D[u] 表示
5. 若 u 與 V 中任一點 v 存在可行邊，且 v 是存在於 Q
6. 則 D[v] = D[u] + W(u、v)，Pi[v] = u
7. 回到步驟 3
8. 完成

程式下載

原碼下載

參考來源：中山大學 九十三學年度電腦程式設計競賽 試題 Problem B