在城市智能交通中,经常会用到最短路径的问题,比如找最佳的行车路线等,Dijkstra算法做为最经典的求解方法,为我们指明了方向.不过真正想让我了解该算法的原因是在学习ICTCLAS的N-最短路径算法,虽然和我们常用的案例有一点区别,但基本相同,为了更好的理解N-最短路径算法,我又重新把大学时代的数据结构知识搬了出来。
在网上找到一篇文章,非常具体生动(有FLASH动画演示)的描述了该算法的实现,不过第一页右下角的图终点那一列2和3弄反了,看的时候要注重 ,具体的算法描述不再赘述,请参考:
http://student.zjzk.cn/course_ware/data_structure/web/tu/tu7.5.1.htm
下面给出我的算法实现具体代码,为了更好的验证程序的正确性,在原来的基础上我又多加了几条边
package sinboy.datastrUCture;
import Java.util.ArrayList;
public class Dijkstra ...{
static ArrayListSide map = null;
...[ 查看全文 ]