Dijkstra-单源最短路径算法

1、算法概述

  Dijkstra算法用来计算一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。

  算法的时间复杂度是$O(n^3)$，它不能处理存在负边权的情况。

  算法描述：

  设起点为s,dis[v]表示从s到v的最短路径长度

• 初始化：$dis[v]=\infty (v\ne s);dis[s]=0$

For(i=1;i<=n;i++){
	1.在没有被访问过的点钟找一个顶点u使得dis[u]是最小的。
	2.u标记为已确定最短路径。
	3.For与u相连的每个未确定最短路径的顶点v
	if(dis[u]+w[u][v]<dis[v]){
		dis[v]=dis[u]+w[u][v];
	}
}

• 算法结束：dis[v]为s到v的最短距离。

2、算法实例

  对于下图，我们想求出从顶点1到其他所有顶点的最短距离。

  算法开始时，我们设置dis[1]=0(自己到自己最短距离肯定是0),其他的点$dis[i]=\infty$。

这里规定两种类型的顶点，代码中可以设置一个boolean数组来表示

• 蓝点：未确定最短路径的点。
• 白点：已经确定最短路径的点

  第一轮，dis[1]=0最小，将1变成白点。对所有的蓝点做出修改。此时由于刚开始其他点在dis数组中都是无穷大，所以只要1能到达的点，我们都会更新，更新之后的dis数组如下(不考虑下标为0):
$$[0,\infty ,\infty ,\infty ,\infty ]->[0,2,4,7,\infty ]$$
  第二轮，dis[2]=2最小，将2变成白点。对蓝点做出修改。

  由于$dis[2]+a[2][3]=2+1=3<dis[3]=4$,则令$dis[3]=3$

  由于$dis[2]+a[2][5]=2+2=4<dis[5]=\infty$,则令$dis[5]=4$
$$[0,2,4,7,\infty ]->[0,2,3,7,4]$$
  第三轮，dis[3]=3最小，将3变成白点。对蓝点做出修改。

  由于$dis[3]+a[3][4]=3+1=4<dis[4]=7$，则令$dis[4]=4$

  由于$dis[3]+a[3][5]=4+6=10>dis[5]=4$,所以不更新dis[5]

  这里给出了此时为什么不更新dis[5]，其他步骤中有关不更新的就不再列出了。

$$[0,2,3,7,4]->[0,2,3,4,4]$$

  第四轮，dis[4]=4最小，将4变成白点。对蓝点做出修改

  此时并不符合更新条件。

  第五轮，dis[5]=4最小，将5变成白点，此时所有的点都是白点了，搜索结束。

  最终的dis数组为:$[0,2,3,4,4]$，数组的值分别表示顶点1到其他各个顶点的最短距离。

3、实战案例

3.1 题目描述

  小明是蓝桥王国的王子，今天是他登基之日。

  在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。

  题目的内容如下：

  蓝桥王国一共有N个建筑和M条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为$1\sim N$。(其中皇宫的编号为1).

  国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。

输入描述

  输入第一行包含两个正整数N,M。

  第2到M+1行每行包含三个正整数u,v,w，表示$u\to v$之间存在一条距离为w的路。
$$1\le N\le 3\times 10^5,1\le m\le 10^6,1\le u_i,v_i\le N,0\le w_i\le 10^9$$
输出描述

  输出仅一行，共N个数，粉笔表示从皇宫到编号为$1\sim N$建筑的最短距离，两两之间用空格隔开。(如果无法到达则输出-1)

输入输出样例

  输入

3 3
1 2 1
1 3 5
2 3 2

  输出

0 1 3

3.2 解题思路与代码实现

  很明显，这是一道求最短路径的题，而且还是单源最短路径，因为只问了从皇宫到其他节点之间的最短距离，那我们使用Dijkstra算法即可很快实现。

import java.util.Arrays;
import java.util.Scanner;

//最短路径，邻接矩阵实现
public class Dijkstra {
    public static int n,m,s;
    static int[][] mp;  //地图：邻接矩阵存储
    static int[] dis;   //dis[v]：从s到v的最短路径长度
    static boolean[] vis;//标记是否已经被访问
    static int[] pre;   //记录前驱，方便最后输出最短路径
    public static void initmp(){
        for (int[] ints : mp) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
    }
    //求源点s到其他点的最短路径
    public static void dijkstra(int s){
        //false表示蓝点(未确定最短路径的带能),true表示白点(确定路径的点)
        Arrays.fill(vis,false);
        //默认情况下设置为无穷大
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[s]=0;   //自己到自己的距离是0
        while(true){
            int mini=0;
            int min_=Integer.MAX_VALUE;
            for (int j = 1; j <=n ; j++) {
                if(!vis[j]&&min_>dis[j]){//从蓝点触发找出最小的点
                    mini=j;
                    min_=dis[j];
                }
            }
            //如果没找到蓝点，说明结束
            if(mini==0){
                break;
            }
            vis[mini]=true; //将当前点mini设置为白点
            for (int i = 1; i <=n ; i++) {
                if(!vis[i] &&dis[i]>dis[mini]+mp[mini][i]){
                    dis[i]=dis[mini]+mp[mini][i];
                    pre[i]=mini;//设置i的前驱为mini
                }
            }
        }
    }
    //求到z的最短路径的路线
    public static void output(int z){
        if(z==0){
            return;
        }
        output(pre[z]);
        System.out.print(z+"->");
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n= scan.nextInt();
        m=scan.nextInt();
        mp=new int[n+1][n+1];
        dis=new int[n+1];
        vis=new boolean[n+1];
        pre=new int[n+1];
        initmp();   //刚开始都设置无穷大
        for (int i = 0; i <m ; i++) {
            //u到v的距离为w
            int u = scan.nextInt();
            int v = scan.nextInt();
            int w = scan.nextInt();
            if(mp[u][v]>w){
                mp[u][v]=mp[v][u]=w;    //无向图
            }
        }
        dijkstra(1);    //1为起始点
        //输出从皇宫到编号为1-N建筑的最短距离
        Arrays.stream(dis).skip(1).forEach(x->{
            System.out.print(x+" ");
        });
//        System.out.println();
//        //从起点出发到每一个点的最短路径如下：
//        for (int i = 1; i <=n ; i++) {
//            output(i);
//            System.out.println();
//        }

    }
}

  这里输出dis数组的时候我们忽略了下标为0的位置，因为我们这里默认下标都是从1开始，方便理解和计算。
  我们还可以输出从节点1开始到其他所有节点的最短路径
文章来源地址https://uudwc.com/A/vm3rj