最短路径 Dijstar 算法

最短路径：对于带权的图来说，最短路径，是指两个顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

应用：单源点到其余各顶点的最短路径问题。

实例应用：

image.png

有无向图，如上，求解某一顶点到其余各顶点的最短路径。代码实现如下：

/**
 * 单源点最短路径算法 Dijstar 算法： 时间复杂度 O(N^2)
 */
public class Dijstar {
    public static int I = 10000;

    /**
     * 存储了图的邻接矩阵。
     * I代表：两个顶点之间无直接通路。
     * 数组下标0、1、2.... 代表了v0、v1、v2的相关值。例如：array[0][1]为1，代表v0 到 v1的权值为1
     */
    private int[][] array = {
        {0,1,5,I,I,I},
        {1,0,3,7,5,I},
        {5,3,0,I,1,7},
        {I,7,I,0,2,I},
        {I,5,1,2,0,3},
        {I,I,7,I,3,0}
    };

    /**
     * 求 vk 到所有顶点的最短路径
     * @param k  0到5s
     */
    public void dijstar(int k){
        /*
         * 初始化
         */
        // weight 数组：某个顶点到所有顶点的最小路的权重值
        int[] weight = array[k];    //初始值为目前vk 到 所有顶点的权值，之后一直不断修正。

        //path 数组：记录了某个顶点到其它所有顶点的前驱顶点。
        int[] path = {};

        //flag 数组：标识所有顶点是否以访问（已计算出最小路径的顶点），取值为1：已访问；0：未访问。
        int[] flag = {};
        flag[k] = 1;  //初始标识vk 已经被访问过。

        //这一层循环的作用： 在剩下的未选中的顶点中，依次选择路径最短的顶点，纳入 选中顶点集合。每次选中一个顶点，预计weight.length 选择完毕。
        for (int i = 0; i < weight.length; i++) {

            /**
             * 遍历一遍 寻找在未选中过的顶点中，距离 源点 路径最小的顶点
             */
            int min = I;
            for (int j = 0; j < weight.length; j++) {
                if (flag[j] == 0 && weight[j] < min){
                    min = weight[j];
                    k = j;
                }
            } //此一轮遍历后，vk为 在未选中过的顶点中，从源点 到所有顶点中 路径权值最短的哪个。

            //将此顶点 纳入 选中的集合。
            flag[k] = 1;

            /*
             * 这里有个逻辑： 假设源点为v0, 且选中的顶点集合：[v0,v1,v2,v3],未选中的顶点集合：[v4,v5]
             * 那么此时 weight[5]的值为：从v0 到 v5，且包括了 经过v1、v2、v3作为跳板 的所有路径中最小的权值（因为v1、v2、v3
             * 加入到选中集合是，都可能修正过weight[5] 的值）。接下来当v4 纳入选中的顶点集合时，也要再次修正
             * weight[5]，看看从v0 到 v5的路径权值是 经过了v4 为跳板的路径权值更小，还是原来的值(经过了v1、v2
             * 、v3为跳板 的最小路径权值)更小，如果经过 v4顶点跳板的路径权值更小，则继续修正weight[5]
             */

            //修正 当前weight的值
            for (int z = 0; z < weight.length; z++) {
                /*
                 * weight[z]：源点到vZ 的路径权值。
                 * min + array[k][z]： 源点到vZ 的路径权值(通过k为跳板的情况)
                 */
                if (flag[z] == 0 && min + array[k][z] < weight[z]){
                    //如果发现通过k 跳板，从源点 到 vZ的路径权值更小，进行修正。
                    weight[z] = min + array[k][z];
                    path[z] = k;    //源点 到vZ 的前驱为 vk
                }
            }

        }
    }

}

理解思路参考：数据结构--Dijkstra