dijkstra算法解析

用一维数组int [] dis 记录V0顶点到各个顶点的最短路径，初始化dis数组后，这个dis数组中储存的每个值都是未定的最短路径值（不知道是不是最短），之后算法的目的是：通过判断和调整dis ，使得最终这个dis数组储存的是V0到每个顶点的确定的最短路径。

判断的依据：在所有未定的最短路径值中，最小未定的最短路径值一定是一个确定的最短路径。

    public static void main(String[] args) {
        int MAX=65536;
        boolean[] isFixed = {true,false,false,false,false,false}; 
// 使用邻接矩阵来存储图
        int[][] weight = {
            {0,7,9,MAX,MAX,14},
            {7,0,10,15,MAX,MAX},
            {9,10,0,11,MAX,2},
            {MAX,15,11,0,6,MAX},
            {MAX,MAX,MAX,6,0,9},
            {14,MAX,2,MAX,9,0}
        };
//初始化最短路径数组
        int dis[] = {0,7,9,MAX,MAX,14};
        
        for(int l1=1;l1<weight.length;l1++) {
            int minWeight=MAX;
            int fixedNode=0;
// 从未定值中找出最小的一个未定值
            for(int l2=0;l2<weight.length;l2++) {
                if(!isFixed[l2]&&minWeight>dis[l2]) {
                    minWeight=dis[l2];
                    fixedNode=l2;
                }
            }
// 最小未定值一定是一个确定的值
            isFixed[fixedNode]=true;
// 对最小未定值连接的边进行松弛操作，更新dis数组
// 在所有剩下的未定值中，只需确保dis数组中下一个最小未定值是正确的即可
            for(int l2=0;l2<weight.length;l2++) {
                if((weight[fixedNode][l2]+dis[fixedNode])<dis[l2]) {
                    dis[l2]=weight[fixedNode][l2]+dis[fixedNode];
                }
            }
        }
// 输出
        for(int l1=0;l1<dis.length;l1++) {
            System.out.println(dis[l1]);
        }
    }