由图论的知识可知,地图上的点构成一带权无向图(有向图可视为特例的一种),要找出任意两地间的最短路径,对地图中的所有点,首先要建立一个邻接矩阵,它表示图中任意两地间的邻接关系及其权值(若两地间无任何连接关系则设为无穷大),易知该矩阵为对称矩阵。从该矩阵出发,可以利用图论中的迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法等求出最短路径。
Dijkstra算法
Dijkstra算法的基本思路是:首先,引进一个辅助向量Dist,它的每个分量Dist [i]表示当前找到的从始点V到每个终点Vi 的最短路径的长度。它的初始值为:若从V到Vi有弧,则Dist [i]为弧上的权值;否则置Dist[i]为无穷大。显然,长度为Dist[i]=Min{Dist[i]|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 不
(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(