suanfa.rar_源码

最短路径算法源码(VB)

　　本人载网站开发 gis,游自编的最短路径查询程序，速度特快，3 万节点，35000 条路全部遍历，只需 1

秒。现将最短路径的思路告诉大家，希望大家在优化，并用不同语言编制，我正在学 delphi,准备用 delphi

做成库，本例以由拓扑关系的 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 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 为网中最大的节点数。

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