单源点最短路径Dijkstra算法的JAVA实现

【 tulaoshi.com - 编程语言 】

　　在城市智能交通中,经常会用到最短路径的问题,比如找最佳的行车路线等,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;

　　    static ArrayListInteger redAgg = null;

　　    static ArrayListInteger blueAgg = null;

　　    static Side[] parents = null;

　　    public static void main(String[] args) ...{
　　        // 初始化顶点集
　　        int[] nodes = ...{ 0, 1, 3, 2, 4, 5,6 };

　　        // 初始化有向权重图
　　        map = new ArrayListSide();
　　        map.add(new Side(0, 1, 10));
　　        map.add(new Side(0, 3, 30));
　　        map.add(new Side(0, 4, 100));
　　        map.add(new Side(1, 2, 50));
　　        map.add(new Side(2, 4, 10));
　　        map.add(new Side(3, 2, 20));
　　        map.add(new Side(3, 4, 60));
　　        map.add(new Side(4, 5, 50));
　　        map.add(new Side(3, 5, 60));
　　        map.add(new Side(5, 6, 10));
　　        map.add(new Side(3, 6, 80));

　　        // 初始化已知最短路径的顶点集，即红点集，只加入顶点0
　　        redAgg = new ArrayListInteger();
　　        redAgg.add(nodes[0]);

　　        // 初始化未知最短路径的顶点集,即蓝点集
　　        blueAgg = new ArrayListInteger();
　　        for (int i = 1; i nodes.length; i++)
　　            blueAgg.add(nodes[i]);

　　        // 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通
　　        parents = new Side[nodes.length];