說明：
1. 如圖 3-1 所示為一交通示意圖，圓圈節點代表城市，並以數字表示其順序；
連接線表示城市間的進行方向，連接線的數字代表成本分 (成本 = 距離 * 時速)。
某君規劃假期將由出發地到目的地(如示意圖，由節點 ① 到節點 ⑦)，假設城市
間之各路段距離及時數可事先查詢完成，則某君在出發前即可將各路段的距離
及時數換算為成本(如示意圖)，據以搜尋最低成本的路徑，並處理得知其所經過
程式節點的先後次序，及其路徑的總和最低成本值。請設計一程式完成之。
範例：
2. 當城市間連接線的成本值改變，仍然可搜尋最低成本的路徑，
並獲得其所經各程式節點的先後次序，及其路徑的總和最低成本值。
說明：
輸入格式：1. 依序以「程式編號 程式編號 城市間連接線的成本數字」表示，
例如由節點 1 到節點 2 的表示為「1 2 35」。餘此類推，將所有城市及城市
間連接線的數字設定完成，並儲存成輸入檔。
輸入檔內容可隨時更改，格式如表 3-2 所示：
可隨時更改輸入檔的成本值，再搜尋最低成本的路徑次序
及其最低成本值。
輸出格式：印出最低成本值總和、其所經各城市節點的先後次序及
其路徑值，如表 3-3 所示：
|
最低成本值總和：180 路徑次序：1 2 4 5 7 連線數值：0 35 30 45 70 |
||||||||||||||||||||||||||||||
表 3-2 |
表 3-3 |
範例二：
1. 節點 6 到 節點 7 的值改為 70，如表 3-4 所示：
輸出格式：印出最低成本值總和、其所經各程式節點的先後次序及
其路徑值，如表 3-5 所示：
|
最低成本值總和：180 路徑次序：1 2 3 6 7 連線數值：0 35 45 20 70 |
||||||||||||||||||||||||||||||
表 3-4 |
表 3-5 |
演算法
1)如果記錄陣列有起點至終點的最短路徑長度, 則傳回去。
2)如果起點與終點是同一點，則傳回長度 0
3)設定最短的路徑長度(min)是不通的(no path)。
4)設定起點已經拜訪過了(避免重複繞路)
5)由起點去拜訪週邊每一個點(該點必須沒拜訪過且有通路)
6)計算路徑 = 地圖相鄰兩點的距離 + 該點到終點的最短距離。
7)比較這點到週邊所有可通的點，找出最小的。(與 min 做比較)
8)當 min 有所更新，則必需記錄該 min 是由 起點至該點產生的。
9)當週邊所有點都拜訪過以後，起點拜訪的旗標設為未拜訪。(要離開起點了)
10)記錄起點至某一點(發生最小的 min 那一點)，到記錄陣列，以備以後使用。
11)傳回前面發生的最小 min。
家豪版
youtube 影音教學
Function DirectedShortestPath(ByVal beginPoint As Integer, ByVal endPoint As Integer) As Integer
Dim i As Integer, lenTemp As Integer, min As Integer
If (minLength(beginPoint, endPoint) <> NoPath) Then 'step 1. 最短路徑存在的話, 就傳回最短路徑
Return (minLength(beginPoint, endPoint))
ElseIf (beginPoint = endpoint) Then 'step 2. 起點與終點一樣, 路徑長是 0
Return (0)
End If
min = NoPath 'step 3. 設定最短距離是不通的
visit(beginPoint) = True 'step 4. 起點拜訪過了
For i = 1 To N 'step 5. 從第 1 點開始拜訪至 N
If (Not visit(i)) Then '如果 i 這點未拜訪的話
If (map(beginPoint, i) <> NoPath) Then '從 起點 到 i 存在路徑的話
'路徑 = 目前地圖資訊 起點至 i 點的長度 + 遞迴搜尋 i 點到目的地的長度
lenTemp = map(beginPoint, i) + DirectedShortestPath(i, endPoint) 'step 6.
If (min > lenTemp) Then '如果路徑比之前 min 短的話 'step 7.
min = lenTemp 'min 記住目前較短的值
getshort(beginPoint) = i 'step 8. 記住路徑從 起點 到 i
End If
End If
End If
Next
visit(beginPoint) = False 'step 9.
minLength(beginPoint, endPoint) = min 'step 10.
Return (min) 'step 11.
End Function
仕隆版(該生當初指導老師不是本人)
這一版是事先先規劃好路徑，把路徑的算法寫成公式，完全沒有演算法概念。
題意只有 4 條路徑，如下：
將四條路徑以陣列存取其和即可。
此方法不是正規演算法，有幾個 bug 很容易看出。
1)增加點，就會錯。
2)增加點到點的路徑，或刪除路徑，就會錯。
3)如果地圖資訊有很多條路徑，最多 C(n,2)，也就是 7 個點，最多 42 個路徑，
此時有把 42 個公式鍵入，不但工程浩大，也容易發生打字錯誤的情況。
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim i, j, tp As Integer
Dim a() As String
Dim b() As String
Dim a1(30) As Integer
'*************************讀檔:先分行 在分個別******************
a = Split(TextBox1.Text, vbNewLine) '讀每行資料
For i = 0 To a.Length - 2
b = Split(a(i), " ") '在讀取個別黨存於陣列中
For j = 0 To 2
a1(tp) = b(j)
tp += 1
Next
j = 0
Next
'***************************************************************
Dim ans(4) As Integer '紀錄每條短路徑
Dim an(4, 5) As Char '紀錄路徑次序
'[-----------路徑1----------------------------------------------------------------
ans(1) = a1(2) + a1(5) + a1(14) + a1(26) '1 2 3 6 7
an(1, 0) = "1" : an(1, 1) = "2" : an(1, 2) = "3" : an(1, 3) = "6" : an(1, 4) = "7"
'[-----------路徑2----------------------------------------------------------------
ans(2) = a1(2) + a1(5) + a1(11) + a1(23) '1 2 3 5 7
an(2, 0) = "1" : an(2, 1) = "2" : an(2, 2) = "3" : an(2, 3) = "5" : an(2, 4) = "7"
'[-----------路徑3----------------------------------------------------------------
ans(3) = a1(2) + a1(8) + a1(17) + a1(23) '1 2 4 5 7
an(3, 0) = "1" : an(3, 1) = "2" : an(3, 2) = "4" : an(3, 3) = "5" : an(3, 4) = "7"
'[-----------路徑4----------------------------------------------------------------
ans(4) = a1(2) + a1(8) + a1(20) '1 2 4 7
an(4, 0) = "1" : an(4, 1) = "2" : an(4, 2) = "4" : an(4, 3) = "7"
Dim min As Integer = 1000 '總最短路徑長
Dim tp1, tp2 As Integer '紀錄最小的陣列位址
For i = 1 To 4
If ans(i) < min Then
min = ans(i)
tp1 = i
End If
Next
'[------判斷是第幾個陣列------
If tp1 = 4 Then '4只有4個
tp2 = 3
Else '其他則是5個
tp2 = 4
End If
'----------------------------]
'[-----------------------輸出--------------------------
TextBox2.Text &= "最低成本數值總和" & min & vbNewLine & "路徑次數 "
For i = 0 To tp2
TextBox2.Text &= an(tp1, i) & " "
Next
TextBox2.Text &= vbNewLine & "連線數值 "
Select Case tp1
Case 1
TextBox2.Text &= "0 " & a1(2) & " " & a1(5) & " " & a1(14) & " " & a1(16)
Case 2
TextBox2.Text &= "0 " & a1(2) & " " & a1(5) & " " & a1(11) & " " & a1(23)
Case 3
TextBox2.Text &= "0 " & a1(2) & " " & a1(8) & " " & a1(17) & " " & a1(23)
Case 4
TextBox2.Text &= "0 " & a1(2) & " " & a1(8) & " " & a1(20)
End Select
End Sub
昊朋版
黃翰版