最短路径算法源码
<FONT size=3>本例以由拓扑关系的arc/info 文件为数据源。其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。<BR>Public Function shortpath(startno As Integer, endno As Integer) As Single<BR>以开始点，结束点为参数。<BR>Dim result() As Single<BR>Dim result1 As Integer<BR>定义结果点<BR>Dim s1 As Single<BR>Dim min As Single<BR>Dim ii, i, j, aa As Integer<BR>Dim yc() As Boolean<BR>Dim ycd() As Boolean<BR>Dim rs1() As Single<BR>Dim no() As Integer<BR>Dim nopoint As Integer<BR>ReDim yc(1 To maxno) As Boolean<BR>ReDim ycd(1 To maxno) As Boolean<BR>ReDim rs1(1 To maxno) As Single<BR>ReDim result(1 To 2, 1 To maxno) As Single<BR>定义结果，其中result(1,maxno)为结果点，result(2,maxno)为结果长度。<BR>For i = 1 To maxno// maxno为网中最大的节点数。<BR>yc(i) = False //标记已经查过的点。<BR>ycd(i) = False //标记已经作结果点用过的点<BR>rs1(i) = 1E+38 //假设从起点到任一点的距离都为无穷大<BR>Next i<BR>ll = startno //设置开始点。<BR>yc(ll) = True //标记开始点为真。即已经作结果点用过。<BR>j = 0<BR>For aa = 1 To maxno<BR>先从与开始点相连的终点寻找 <BR>For i = 1 To indexa1(2, ll) //以与ll点相连的起点的个数循环<BR>result1 = b1(indexa1(1, ll) - i + 1)找出与LL点相连的终点的点号<BR>s1 = c1(indexa1(1, ll) - i + 1) + result(2, ll)找出长度并求和<BR>If yc(result1) = True Then GoTo 200如果以被经查过进行下一个<BR>If ycd(result1) = True Then//如果已经作为结果点判断哪一个长<BR>If rs1(result1) >= s1 Then//如果这一点到起点的长度比现在的路线长，替代<BR>rs1(result1) = s1<BR>result(1, result1) = ll//设置到这点的最短路径的前一点为LL点（精华部分）<BR>result(2, result1) = s1设置到这点的最短路径长度<BR>GoTo 200<BR>Else<BR>GoTo 200<BR>End If<BR>End If<BR>如果上面的条件都不符合则进行下面的语句<BR>ycd(result1) = True<BR>rs1(result1) = s1<BR>result(1, result1) = ll<BR>result(2, result1) = s1<BR>每找到一个点加一，为了下面的判断<BR>j = j + 1<BR>ReDim Preserve no(1 To j) As Integer<BR>从新 定义数组并使其值为当前的点号<BR>no(j) = result1<BR>200 Next I<BR>再从与开始点相连的终点寻找，与上面一样不再标注 <BR>For i = 1 To indexb2(2, ll)<BR>result1 = a2(indexb2(1, ll) - i + 1)<BR>s1 = c2(indexb2(1, ll) - i + 1) + result(2, ll)<BR>If yc(result1) = True Then GoTo 300<BR>If ycd(result1) = True Then<BR>If rs1(result1) >= s1 Then<BR>rs1(result1) = s1<BR>result(1, result1) = ll<BR>result(2, result1) = s1<BR>GoTo 300<BR>Else<BR>GoTo 300<BR>End If<BR>End If<BR>ycd(result1) = True<BR>rs1(result1) = s1<BR>result(1, result1) = ll<BR>result(2, result1) = s1<BR>j = j + 1<BR>ReDim Preserve no(1 To j) As Integer<BR>no(j) = result1<BR>300 Next I<BR><BR>设置最小为无穷大，最短路径点为空<BR>min = 1E+38<BR>minpoint = Null<BR>（优化部分）<BR>找出已经查过点中长度最短的点<BR>For i = aa To j<BR>If min > rs1(no(i)) Then<BR>ii = i<BR>min = rs1(no(i))<BR>minpoint = no(i)<BR>End If<BR>Next I<BR>如果没有结果，即起点与终点没有通路退出程序<BR>If min = 1E+38 Then Exit Function<BR>（重点优化）将两点互换，减少循环。<BR>no(ii) = no(aa)<BR>no(aa) = minpoint<BR>标记已经作为结果点判断过<BR>yc(minpoint) = True<BR>ll = minpoint<BR>判断结果点是否等于终点，如果等于则已经找到最短路径<BR>If minpoint = endno Then Exit For<BR>Next aa<BR>返回最短路径长度<BR>Stpath = result(2, endno)<BR>End Function </FONT><BR> 呵呵，very 感谢
页:
[1]