Dijkstra算法实现

1. 算法简介

• 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
• 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
• 引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
• 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

2. 算法图解

• 选定A节点初始化，如下图所示：

• 找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( ‘D 到 B,C,E 的距离’ + ‘AD 距离’ < ‘A 到 B,C,E 的距离’ )来更新U集合：

• 这时候 A->B, A->C都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' )，如图所示，这时候A->B距离 其实为 A->D->B：

• 思路就是这样，往后就是大同小异了：

• 算法结束：

3. 代码实现

public class Dijkstra {
    public static final int M = 100000; // 代表正无穷

    /**
     *
     * @param start  起点的编号start
     * @param weight 有向图的权重矩阵
     * @return       start到每个点的最短路径
     */
    public static  int[] dij(int start, int[][] weight){
        int n = weight.length;
        int distance[] = new int[n];//保存start点到其他点的最短距离
        String path[] = new String[n];//保存start到其他点的最短路径字符串信息
        for (int i = 0; i < n; i++)
            path[i] = new String(start + "-->" + i);
        int visited[] = new int[n];//标记该点是否已求出，1表示求出

        //初始化，第一个点已经求出
        distance[start] = 0;
        visited[start] = 1;

        // 求start到其余n-1个点
        for(int i=1; i<n; i++){
            int k =-1; //存放一个距离start最近的未标记顶点
            int min = 10000;
            for(int j=0; j<n; j++){
                if(visited[j]==0 && weight[start][j]<min){
                    min = weight[start][j];
                    k = j;
                }
            }
            // 已求得start到第k个点，标记并保存距离
            distance[k] = min;
            visited[k] = 1;
            // 根据之前求的k点更新start到其余点的距离
            for(int j=0; j<n; j++){
                if(visited[j]==0 && weight[start][k]+weight[k][j]<weight[start][j]){
                    weight[start][j] = weight[start][k]+weight[k][j];
                    path[j] = path[k]+"-->"+j;
                }
            }
        }
        for (int i = 0; i < n; i++) {

            System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i]);
        }
        System.out.println("=====================================");
        return  distance;

    }

    public static void main(String[] args) {
        // 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
        // 点到自身距离为0, M为正无穷
        int[][] weight1 = {
                {0,4,M,2,M},
                {4,0,4,1,M},
                {M,4,0,1,3},
                {2,1,1,0,7},
                {M,M,3,7,0}
        };

        int start = 0;

        int[] shortPath = dij(start, weight1);

        for (int i = 0; i < shortPath.length; i++)
            System.out.println("从" + start + "出发到" + i + "的最短距离为：" + shortPath[i]);
    }
}