單源點最短路徑Dijkstra算法的JAVA實現

　　在城市智能交通中,經常會用到最短路徑的問題,比如找最佳的行車路線等,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 ArrayList<Side> map = null;

　　    static ArrayList<Integer> redAgg = null;

　　    static ArrayList<Integer> blueAgg = null;

　　    static Side[] parents = null;

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

　　        // 初始化有向權重圖
　　        map = new ArrayList<Side>();
　　        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 ArrayList<Integer>();
　　        redAgg.add(nodes[0]);

　　        // 初始化未知最短路徑的頂點集,即藍點集
　　        blueAgg = new ArrayList<Integer>();
　　        for (int i = 1; i < nodes.length; i++)
　　            blueAgg.add(nodes[i]);

　　        // 初始化每個頂點在最短路徑中的父結點,及它們之間的權重,權重-1表示無連通
　　        parents = new Side[nodes.length];