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