资源描述：
《最短路径算法源码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最短路径算法源码(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
2、时对应某一终点与其相连的起点的个数，即其拓扑关系。PublicFunctionshortpath(startnoAsInteger,endnoAsInteger)AsSingle以开始点，结束点为参数。Dimresult()AsSingleDimresult1AsInteger定义结果点Dims1AsSingleDimminAsSingleDimii,i,j,aaAsIntegerDimyc()AsBooleanDimycd()AsBooleanDimrs1()AsSingleDimno()AsIntege
3、rDimnopointAsIntegerReDimyc(1Tomaxno)AsBooleanReDimycd(1Tomaxno)AsBooleanReDimrs1(1Tomaxno)AsSingleReDimresult(1To2,1Tomaxno)AsSingle定义结果，其中result(1,maxno)为结果点，result(2,maxno)为结果长度。Fori=1Tomaxno//maxno为网中最大的节点数。yc(i)=False//标记已经查过的点。ycd(i)=False//标记已经作结果点用
4、过的点rs1(i)=1E+38//假设从起点到任一点的距离都为无穷大Nextill=startno//设置开始点。yc(ll)=True//标记开始点为真。即已经作结果点用过。j=0Foraa=1Tomaxno先从与开始点相连的终点寻找 Fori=1Toindexa1(2,ll)//以与ll点相连的起点的个数循环result1=b1(indexa1(1,ll)-i+1)找出与LL点相连的终点的点号s1=c1(indexa1(1,ll)-i+1)+result(2,ll)找出长度并求和Ifyc(result1
5、)=TrueThenGoTo200如果以被经查过进行下一个Ifycd(result1)=TrueThen//如果已经作为结果点判断哪一个长Ifrs1(result1)>=s1Then//如果这一点到起点的长度比现在的路线长，替代rs1(result1)=s1result(1,result1)=ll//设置到这点的最短路径的前一点为LL点（精华部分）result(2,result1)=s1设置到这点的最短路径长度GoTo200ElseGoTo200EndIfEndIf如果上面的条件都不符合则进行下面的语句yc
6、d(result1)=Truers1(result1)=s1result(1,result1)=llresult(2,result1)=s1每找到一个点加一，为了下面的判断j=j+1ReDimPreserveno(1Toj)AsInteger从新定义数组并使其值为当前的点号no(j)=result1200NextI再从与开始点相连的终点寻找，与上面一样不再标注 Fori=1Toindexb2(2,ll)result1=a2(indexb2(1,ll)-i+1)s1=c2(indexb2(1,ll)-i+1)
7、+result(2,ll)Ifyc(result1)=TrueThenGoTo300Ifycd(result1)=TrueThenIfrs1(result1)>=s1Thenrs1(result1)=s1result(1,result1)=llresult(2,result1)=s1GoTo300ElseGoTo300EndIfEndIfycd(result1)=Truers1(result1)=s1result(1,result1)=llresult(2,result1)=s1j=j+1ReDimPres
8、erveno(1Toj)AsIntegerno(j)=result1300NextI设置最小为无穷大，最短路径点为空min=1E+38minpoint=Null（优化部分）找出已经查过点中长度最短的点Fori=aaTojIfmin>rs1(no(i))Thenii=imin=rs1(no(i))minpoint=no(i)EndIfNextI如果没有结果，即起点与终点没有通路退出程序Ifmin=1E+38Then
