由图论的知识可知，地图上的点构成一带权无向图(有向图可视为特例的一种)，要找出任意两地间的最短路径,对地图中的所有点，首先要建立一个邻接矩阵，它表示图中任意两地间的邻接关系及其权值(若两地间无任何连接关系则设为无穷大)，易知该矩阵为对称矩阵。从该矩阵出发，可以利用图论中的迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法等求出最短路径。

Dijkstra算法

Dijkstra算法的基本思路是：首先，引进一个辅助向量Dist，它的每个分量Dist [i]表示当前找到的从始点V到每个终点Vi 的最短路径的长度。它的初始值为:若从V到Vi有弧，则Dist [i]为弧上的权值;否则置Dist[i]为无穷大。显然，长度为Dist[i]=Min{Dist[i]|Vi

V}的路径就是从V出发的长度最短的一条路径。此路径为(V, V j )。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径(设其终点为X)或者是弧(V, X)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度为：Dist[i]=Min{Dist[i]|Vi

S}，其中Dist[i]或者是弧(V, Vi)上权值，或者是Dist[k] (Vk

S)和弧(Vk, Vi)上的权值之和。

Dijkstra算法描述为：

(1) 假设用带权的邻接矩阵Cost来表示带权有向图，Cost[i,j]表示弧(Vi , V j)上权值。若(Vi,Vj)不存在，则置Cost[i,j]为无穷大。S为已找到从V出发的最短路径的终点的集合，它的初始状态为空集。

(2) 选择Vj，使得Dist [i] =Min {Dist [i] |Vi 不

S, Vi

V} , Vj就是当前求得的一条从V出发的最短路径的终点。令S=S U { j}(标记j)。(3) 修改从出发到集合V-S上所有顶点Vk可达的最短路径长度。如果Dist[j] Cost[j, k]

(4) 重复操作(2) , (3)共N-1次。由此求得从V到图上其余各顶点的最短路径是依路径长度递增的序列。

弗洛伊德算法

弗洛伊德算法能够求得每一对顶点之间的最短路径，其基本思想是：假设从顶点Vi到Vj的最短路径。若从Vi到Vj有弧，则从Vi到Vj存在一条长度为COST [ i, j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径(Vi, V1, Vj)是否存在(即判别弧(Vi, V1)和弧(V1, Vj)是否存在)。如果存在，则比较(Vi, Vj)和(Vi, V1, Vj)的路径长度，较短者为从Vi到Vj的中点顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点V2，也就是说，若(Vi，…，V2)和(V2，...，Vj)分别是当前找到的中间顶点的序号不大于1的最短路径，那么(Vi，...，V2，...，Vj)就有可能是从Vi到Vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从Vi 到Vj的中间顶点的序号不大于1的最短路径相比较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点V3，继续进行试探。依次类推，在经过n次比较之后，最后求得的必是从Vi 到Vj的最短路径。按此方法，可同时求得各对顶点间的最短路径。算法共需3层循环，总的时间复杂度是O(

) 。 2100433B