随着知识经济的到来,信息将成为人类社会财富的源泉,网络技术的飞速发
展与广泛应用带动了全社会对信息技术的需求,最短路径问题作为许多领域中选
择最有问题的基础,在电子导航,交通旅游,城市规划以及电力、通讯等各种管
网、管线的布局设计中占有重要地位。
最短路径,顾名思义就是在所有的路径中找到距离最短的路径,而我们所说
的最短路径通常不仅仅指地理意义的距离最短,还可以引申到其他的度量,如时
间、费用、路线容量等。相应地,最短路径问题就成为最快路径问题,最低费用
问题等,所以我们所说的最短路径也可以看做是最优路径问题。
最短路径问题在交通网络结构的分析,交通运输线路的选择,通讯线路的选
择与维护,运输货流的最小成本分析,城市公共交通网络的规划等,都有直接应
用的价值。最短路径问题在实际中还应用于汽车导航系统以及各种应急系统等,
这些系统一般要求计算出到出事点的最佳线路,在车辆行驶过程中还需要实时的
计算出车辆前方的行驶路线,这就决定了最短路径问题的实现应该是高效的。
最短路径问题一直是计算机学科,运筹学,交通工程学,地理信息学等学科
的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结
合使得新的最短路径算法不断的涌现。