最短路径算法在交通咨询系统中的应用.pdf

开发与应用 计算机与信息技术 ·23· 最短路径算法在交通咨询系统中的应用 高寒弢 秦士琨 刘元梓 （61920 部队，四川 成都 610505） 摘 要 最短路径问题在交通调度、车辆导航等实际应用中有着重要的意义。本文阐述了迪杰斯特拉算法求最短路径 的方法，并给出了迪杰斯特拉算法在交通咨询系统中的应用实现方法。 关键词 最短路径；最短路径应用；交通咨询；Dijkstra 算法 1 引言 路径长度。它的初态为：若从 v 到 vi 有弧，则 D [i] 为弧上的 最短路径问题在计算机科学、运筹学、交通工程学、地 权值；否则置 D [i] 为 ∞。显然，长度为 理信息系统等学科中是一个研究的热点，它是资源分配、线 D [ j ] Min {D [i ] | v i ∈V } i 路选择等问题解决的基础，尤其是在诸如地图、车辆调度和 的路径就是从 v 出发的长度最短的一条最短路径。此路径为 路由选择方面有着广泛的应用。本文就最短路径算法在交通 v v （ ， j ）。 咨询系统中的应用进行了分析和实现。 那么，下一条长度次短的最短路径是哪一条呢。假设该 2 最短路径算法 次短路径的终点是 vk ，则可想而知，这条路径或者是（v ， 在求解网络图中节点间最短路径的方法中，目前国内外 vk ），或者是（v ，vj ，vk ）。它的长度或者是从v 到 vk 的 一直公认的较好的算法有迪杰斯特拉（Dijkstra）算法和弗洛 弧上的权值，或者是 D [j ]和从 vj 到 vk 的弧上的权值之和。 伊德（Floyd）算法及启发式 A * 算法。前两种算法中，网络被 一般情况下，假设 S 为已求得最短路径的终点的集合， 抽象为一个图论中定义的有向或无向图，并利用图中节点邻 则可证明：下一条最短路径（设其终点为 x ）或者是弧（v ， 接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路 x ），或者是中间只经过S 中的顶点而最后到达顶点 x 的路 径时以该矩阵为基础不断进行目标值的最小性判别，直到获 径。 得最后的优化路径。启发式 A * 算法采用一个代价函数，只有 因此，在一般情况下，下一条长度次短的最短路径的长 代价函数范围内的点才会被遍历，可以有效地缩小搜索的 度必是 范围。