最短路径算法源码(VB) 集锦

本例以由拓扑关系的arc/info 文件为数据源。其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点

与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。

Public Function shortpath(startno As Integer, endno As Integer) As Single

以开始点，结束点为参数。 Dim result() As Single Dim result1 As Integer

定义结果点 Dim s1 As Single Dim min As Single Dim ii, I, j, aa As Integer Dim yc() As Boolean Dim ycd() As Boolean Dim rs1() As Single Dim no() As Integer Dim nopoint As Integer ReDim yc(1 To maxno) As Boolean ReDim ycd(1 To maxno) As Boolean ReDim rs1(1 To maxno) As Single ReDim result(1 To 2, 1 To maxno) As Single

定义结果，其中result(1,maxno)为结果点，result(2,maxno)为结果长度。

For I = 1 To maxno// maxno为网中最大的节点数。

Yc(i) = False //标记已经查过的点。 Ycd(i) = False //标记已经作结果点用过的点 rs1(i) = 1E+38 //假设从起点到任一点的距离都为无穷大

Next I

ll = startno //设置开始点。

Yc(ll) = True //标记开始点为真。即已经作结果点用过。

J = 0

For aa = 1 To maxno 先从与开始点相连的终点寻找

For I = 1 To indexa1(2, ll) //以与ll点相连的起点的个数循环

result1 = b1(indexa1(1, ll) - I + 1)找出与LL点相连的终点的点号 s1 = c1(indexa1(1, ll) - I + 1) + result(2, ll)找出长度并求和 If yc(result1) = True Then GoTo 200如果以被经查过进行下一个 If ycd(result1) = True Then//如果已经作为结果点判断哪一个长 If rs1(result1) >= s1 Then//如果这一点到起点的长度比现在的路线长，替代

rs1(result1) = s1

result(1, result1) = ll//设置到这点的最短路径的前一点为LL点（精华部分）

result(2, result1) = s1设置到这点的最短路径长度

GoTo 200 Else GoTo 200 End If End If

如果上面的条件都不符合则进行下面的语句

ycd(result1) = True rs1(result1) = s1 result(1, result1) = ll result(2, result1) = s1

每找到一个点加一，为了下面的判断

j = j + 1

ReDim Preserve no(1 To j) As Integer 从新 定义数组并使其值为当前的点号

no(j) = result1 200 Next I

再从与开始点相连的终点寻找，与上面一样不再标注

For I = 1 To indexb2(2, ll) result1 = a2(indexb2(1, ll) - I + 1) s1 = c2(indexb2(1, ll) - I + 1) + result(2, ll) If yc(result1) = True Then GoTo 300

If ycd(result1) = True Then If rs1(result1) >= s1 Then

rs1(result1) = s1

result(1, result1) = ll result(2, result1) = s1

GoTo 300 Else GoTo 300 End If End If ycd(result1) = True rs1(result1) = s1 result(1, result1) = ll result(2, result1) = s1

j = j + 1

ReDim Preserve no(1 To j) As Integer

no(j) = result1 300 Next I

设置最小为无穷大，最短路径点为空

min = 1E+38 minpoint = Null （优化部分）

找出已经查过点中长度最短的点

For I = aa To j If min > rs1(no(i)) Then

ii = I min = rs1(no(i)) minpoint = no(i)

End If Next I

如果没有结果，即起点与终点没有通路退出程序

If min = 1E+38 Then Exit Function （重点优化）将两点互换，减少循环。

No(ii) = no(aa)

no(aa) = minpoint 标记已经作为结果点判断过

yc(minpoint) = True

ll = minpoint

判断结果点是否等于终点，如果等于则已经找到最短路径

If minpoint = endno Then Exit For

Next aa 返回最短路径长度 Stpath = result(2, endno)

End Function

-----------------------------------------------------------------------------------------

最短路径程序

Option Explicit Dim p(7) As rcd Dim Matrix(7, 7) As Integer

Private Sub Command2_Click()

End End Sub

Function seekSmall(a() As Integer)

Dim n, k, m, i, j As Integer

n = UBound(a) - 2

i = 1 m = a(0, 1): k = 0 Do While a(i, 1) <> 0 If a(i, 1) < m Then m = a(i, 1): k = i

End If i = i + 1 Loop seekSmall = k

Print End Function

Private Sub cmdContinue_Click() MsgBox \请输入要求的路径\txtStart.Text = \

txtPath.Text = \

End Sub

Private Sub cmdEnd_Click()

End End Sub

Private Sub cmdOk_Click() Dim nS, nE As Integer Dim h As String Dim i, j As Integer Dim n As Integer Dim x, y, z As Integer

If txtStart.Text <> \

nS = Val(txtStart.Text) - 1: nE = Val(txtEnd.Text) - 1 '确定起始点

If (nS > 6 Or nE > 6) Then

MsgBox \没有该点，请重新输入正确的点\

End If Else

MsgBox \没有输入\

End If

p(0).iN = nS '记录起始点

n = 0 For j = 0 To 6 If j <> nS Then p(0).fT(n, 0) = j p(0).fT(n, 1) = Matrix(nS, j)

n = n + 1 End If Next j

p(0).jN = seekSmall(p(0).fT())

Print p(0).Judge = True

n = 0 For j = 0 To 6

If (j <> p(0).fT(p(0).jN, 0)) And (j <> nS) Then

p(0).bT(n, 0) = j p(0).bT(n, 1) = Matrix(nS, j)

n = n + 1 End If Next j For i = 1 To 5

p(i).iN = p(i - 1).fT(p(i - 1).jN, 0)

For j = 0 To 5 - i

If ((p(i - 1).bT(j, 1) >= (p(i - 1).fT(p(i - 1).jN, 1) + Matrix(p(i).iN, p(i - 1).bT(j, 0)))) And ((p(i -

1).fT(p(i - 1).jN, 1)) + Matrix(p(i).iN, p(i - 1).bT(j, 0)) < 100)) Then

If p(i - 1).bT(j, 0) = nE Then

If p(i - 1).bT(j, 1) >= (p(i - 1).fT(p(i - 1).jN, 1) + Matrix(p(i).iN, p(i - 1).bT(j, 0))) Then

p(i).Judge = True

End If End If

p(i).fT(j, 1) = (p(i - 1).fT(p(i - 1).jN, 1) + Matrix(p(i).iN, p(i - 1).bT(j, 0)))

p(i).fT(j, 0) = p(i - 1).bT(j, 0)

Else

p(i).fT(j, 1) = p(i - 1).bT(j, 1) p(i).fT(j, 0) = p(i - 1).bT(j, 0)

End If

If p(i).fT(j, 0) = nE Then If p(i).fT(j, 1) > 100 Then p(i).Judge = True

End If End If Next j

p(i).jN = seekSmall(p(i).fT())

n = 0 For j = 0 To 5 - i If p(i).jN <> j Then p(i).bT(n, 0) = p(i).fT(j, 0) p(i).bT(n, 1) = p(i).fT(j, 1)

n = n + 1 End If Next j Next i For i = 0 To 5 If p(i).iN = nE Then For j = 0 To i

If p(j).Judge = True Then h = h & (p(j).iN + 1) & \

End If Next j

txtLength.Text = p(i - 1).fT(nS, 1) ElseIf i = 5 And p(i).iN <> nE Then

For j = 0 To 5

If p(j).Judge = True Then h = h & (p(j).iN + 1) & \

End If Next j

txtLength.Text = p(5).fT(nS, 1)

End If Next i

txtPath.Text = h & nE + 1 'Open \

'For z = 0 To 5 'Print #1,

'Print #1, \

'Print #1, ' Print #1, p(z).iN ' For x = 0 To 5 - z ' For y = 0 To 1 ' Print #1, p(z).fT(x, y);

' Next y ' Next x ' Print #1, ' Print #1, p(z).jN ' For x = 0 To 4 - z ' For y = 0 To 1 ' Print #1, p(z).bT(x, y);

' Next y ' Next x 'Next z 'For x = 0 To 6

'Print #1, 'Print #1, p(x).Judge

'Next x 'Close End Sub

Private Sub cmdOpen_Click()

Dim i, j As Integer On Error GoTo a: With CommonDialog1

.Filter = \文本文件（*.txt）|*.txt|所有文件（*.*）|*.*\

.ShowOpen End With

Open CommonDialog1.FileName For Input As #1

txtEdit.Text = Input(LOF(1), 1)

Close #1

Open CommonDialog1.FileName For Input As #1

Do While Not EOF(1) For i = 0 To 6 For j = 0 To 6 Input #1, Matrix(i, j)

Next j Next i Loop Close a: End Sub

本文来源：https://www.bwwdw.com/article/kfcx.html