Dijkstra-单源最短路径算法

1、算法概述2、算法实例3、实战案例3.1 题目描述3.2 解题思路与代码实现

1、算法概述

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

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

算法描述：

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

初始化： d i s [ v ] = ∞ ( v ≠ s ) ; d i s [ s ] = 0 dis[v]=\infty (v \neq s);dis[s]=0 dis[v]=∞(v=s);dis[s]=0

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

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

2、算法实例

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

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

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

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

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

[ 0 , ∞ , ∞ , ∞ , ∞ ] − > [ 0 , 2 , 4 , 7 , ∞ ] [0,\infty,\infty,\infty,\infty ]->[0,2,4,7,\infty] [0,∞,∞,∞,∞]−>[0,2,4,7,∞]

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

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

由于 d i s [ 2 ] + a [ 2 ] [ 5 ] = 2 + 2 = 4 < d i s [ 5 ] = ∞ dis[2]+a[2][5]=2+2=4<dis[5]=\infty dis[2]+a[2][5]=2+2=4<dis[5]=∞,则令 d i s [ 5 ] = 4 dis[5]=4 dis[5]=4

[ 0 , 2 , 4 , 7 , ∞ ] − > [ 0 , 2 , 3 , 7 , 4 ] [0,2,4,7,\infty]->[0,2,3,7,4] [0,2,4,7,∞]−>[0,2,3,7,4]

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

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

由于 d i s [ 3 ] + a [ 3 ] [ 5 ] = 4 + 6 = 10 > d i s [ 5 ] = 4 dis[3]+a[3][5]=4+6=10>dis[5]=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 ] [0,2,3,7,4]->[0,2,3,4,4] [0,2,3,7,4]−>[0,2,3,4,4]

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

此时并不符合更新条件。

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

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

3、实战案例

3.1 题目描述

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

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

题目的内容如下：

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

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

输入描述

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

第2到M+1行每行包含三个正整数u,v,w，表示 u → v u\to v u→v之间存在一条距离为w的路。

1 ≤ N ≤ 3 × 1 0 5 , 1 ≤ m ≤ 1 0 6 , 1 ≤ u i , v i ≤ N , 0 ≤ w i ≤ 1 0 9 1\le N\le 3\times10^5,1\le m\le10^6,1\le u_i,v_i\le N,0\le w_i \le 10^9 1≤N≤3×105,1≤m≤106,1≤ui​,vi​≤N,0≤wi​≤109

输出描述

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

输入输出样例

输入

3 31 2 11 3 52 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; //自己到自己的距离是0while(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的距离为wint 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开始到其他所有节点的最短路径