[科技论文网] http://www.scipapers.com    2007-12-01  

最短路径算法源码

Public Function ShortPathSearch(NoNode1 As Integer, NoNode2 As Integer, nNode As Integer, NoNode() As Integer, LinkN() As Integer, LinkNi() As Integer, LinkNo() As Integer, LinkDis() As Double, nNodeShortPath As Integer, NodeShortPath() As Integer, ShortPath As Double)
Dim II As Integer, I As Integer, J As Integer, LL As Integer, iLL As Integer
Dim iNode As Integer
Dim S As Single, MinS As Single, MinPoint As Integer
Dim NodeCheck() As Boolean '标记已经查过的点
Dim NodeUse() As Boolean '标记已经作为结果点使用过的点
Dim RS() As Single '假设从起点到任一点的距离都为无穷大
Dim result() As Single '存放结果长度
Dim ResultNo() As Integer '存放结果节点编号
Dim iResult As Integer
Dim No() As Integer
Dim StartNo As Integer, EndNo As Integer
'Begin根据编码，搜索序号
StartNo = 0 EndNo = 0
For I = 1 To nNode
If (NoNode(I) = NoNode1) Then
StartNo = I
End If
If (NoNode(I) = NoNode2) Then
EndNo = I
End If
If (StartNo > 0 And EndNo > 0) Then Exit For
Next I
'End根据编码，搜索序号
ReDim NodeCheck(1 To nNode), NodeUse(1 To nNode)
ReDim RS(1 To nNode), result(1 To nNode), ResultNo(1 To nNode)
For I = 1 To nNode
NodeCheck(I) = False '标记未经查过的点。
NodeUse(I) = False '标记未作为结果点使用过的点
RS(I) = 1E+38 '假设从起点到任一点的距离都为无穷大
Next I
LL = StartNo '设置开始点。
NodeUse(LL) = True '标记开始点为真。即已经作为结果点使用过。
J = 0
For iNode = 1 To nNode
'先从与开始点相连的起点寻找
For I = 1 To LinkN(LL) '以与LL点相连的起点的个数循环
iLL = LinkNi(LL) + I - 1
iResult = LinkNo(iLL) '找出与LL点相连的起点的点号
If NodeCheck(iResult) = False Then '如果没查过，则进行
S = LinkDis(iLL) + result(LL) '找出长度并求和
If NodeUse(iResult) = True Then
'如果已经作为结果点，判断哪一个长
If S <= RS(iResult) Then
'如果这一点到起点的长度比现在的路线长，替代
RS(iResult) = S
result(iResult) = S
'设置到这点的最短路径长度
ResultNo(iResult) = LL
End If
Else
'如果上面的条件都不符合，则进行下面的语句
NodeCheck(iResult) = True
RS(iResult) = S
result(iResult) = S
ResultNo(iResult) = LL
J = J + 1 '每找到一个点加一，为了下面的判断
ReDim Preserve No(1 To J)
'重新定义数组并使其值为当前的点号
No(J) = iResult
End If
End If
Next I
'设置最小为无穷大，最短路径点为空
MinS = 1E+38
MinPoint = 0
'找出已经查过点中长度最短的点
For I = iNode To J
If RS(No(I)) < MinS Then
II = I
MinS = RS(No(I))
MinPoint = No(I)
End If
Next I
'如果没有结果，即起点与终点没有通路，则退出程序
If MinS = 1E+38 Then
MsgBox "即起点与终点没有通路!", vbOKOnly, "关于搜索最短路径"
Exit Sub
End If
'将两点互换，减少循环。
No(II) = No(iNode)
No(iNode) = MinPoint
'标记已经作为结果点判断过
NodeUse(MinPoint) = True
LL = MinPoint
'判断结果点是否等于终点，如果等于则已经找到最短路径
If MinPoint = EndNo Then Exit For
Next iNode
'Begin检索最短路径节点
ReDim NodeShortPath(1 To nNode)
nNodeShortPath = 1
LL = MinPoint
NodeShortPath(nNodeShortPath) = LL
Do
LL = ResultNo(LL)
nNodeShortPath = nNodeShortPath + 1
NodeShortPath(nNodeShortPath) = LL
If (LL = StartNo) Then Exit Do
Loop
'End检索最短路径节点
ShortPath = result(EndNo)
End Sub

    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。