Dijkstra求最短路（图解）

你好，我是Hasity。

今天分享的内容：Dijkstra求最短路这个题目

Dijkstra求最短路I

题目描述

给定一个 n个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500,
1≤m≤10⁵,
图中涉及边长均不超过10000。

示例：

思路分析

迪杰斯特拉算法采用的是一种贪心的策略。求源点到其余各点的最短距离步骤如下：

1. 用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。
   用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。

2. 源点到源点的距离为 0。即dist[1] = 0。

3. 遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离，state[i] 置为 1。

4. 遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist[i] 加上 i -> j 的距离，即 dist[j] > dist[i] + w[i][j]（w[i][j] 为 i -> j 的距离） ，则更新 dist[j] = dist[i] + w[i][j]。

5. 重复 3 4 步骤，直到所有节点的状态都被置为 1。

• 更新与序号1相连接的节点(2,3,4)的dist，离源点1距离最近的状态为0的节点是2，将节点2的state改为1，更新与序号2相连接的节点5的dist

• 离源点1距离最近的状态为0的的节点是4，将节点4的state改为1，更新与序号4相连接的节点5的dist

• 离源点1距离最近的状态为0的的节点是3，将节点3的state改为1，更新与序号3相连接的节点4的dist

• 离源点1距离最近的状态为0的的节点是5，将节点5的state改为1，更新与序号5相连接的节点的的dist（没有也需要遍历一遍）

6. 此时 dist 数组中，就保存了源点到其余各个节点的最短距离。

思考：我们用什么数据结构表示图的任意顶点之间的连接关系呢？

邻接表和邻接矩阵是图的两种常用存储表示方式，用于记录图中任意两个顶点之间的连通关系，包括权值。

对于无向图 graph和有向图digraph

• 选择一：邻接表

无向图 graph 表示

有向图 digraph 表示

• 选择二：邻接矩阵

无向图 graph 表示

有向图 digraph 表示

由题中的1≤n≤500的数据量较小，我们采用邻接矩阵的方法代码更容易实现

关于领接表的优缺点：大家可以看这一篇文章：

代码实现

import java.util.*;
public class Main{
    static int N = 510,n,m, max = 0x3f3f3f3f;
    static int[][] g = new int[N][N];//存每个点之间的距离
    static int[] dist = new int[N];//存每个点到起点之间的距离
    static boolean[] st = new boolean[N];//存已经确定了最短距离的点
    public static int dijkstra(){
        Arrays.fill(dist,max);//将dist数组一开始赋值成较大的数
        dist[1] = 0; //首先第一个点是零

        //从0开始,遍历n次，一次可以确定一个最小值
        for(int i = 0 ; i < n ; i ++ ){ 
            int t = -1; //t这个变量,准备来说就是转折用的
            for(int j = 1 ; j <= n ; j ++ ){
                /***
                 * 因为数字是大于1的，所以从1开始遍历寻找每个数
                 * 如果s集合中没有这个数
                 * 并且t == -1，表示刚开始 或者 后面的数比我心找的数距离起点的距离短
                 * 然后将j 的值赋值给 t
                 ***/
                if(!st[j] && (t == -1 || dist[j] < dist[t])){
                    t = j; 
                }
            }

            st[t] = true;//表示这个数是已经找到了确定了最短距离的点

            //用已经确认的最短距离的点来更新后面的点
            //就是用1到t的距离加上t到j的距离来更新从1到j的长度
            for(int j = 1 ; j <= n ; j ++ ){
                //
                dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
            }
        }
        //如果最后n的长度没有改变，输出-1，没有找到；否则输出最短路n
        if(dist[n] == max) return -1;
        else return dist[n];

    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        //将他们每个点一开始赋值成一个较大的值
        for(int i = 1 ; i <= n ; i ++ ){
            Arrays.fill(g[i],max);
        }
        while(m -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            g[a][b] = Math.min(g[a][b],c);//这个因为可能存在重边，所以泽出最短的
        }
        int res = dijkstra();
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

Dijkstra求最短路 II

题目描述

给定一个 n个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n,m≤1.5×10⁵
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10⁹。

示例：

思路分析

这道题和上一道没有什么区别，差别只有数据范围的变化

第一题：

1≤n≤500,
1≤m≤10⁵,
图中涉及边长均不超过10000。

第二题：

1≤n,m≤1.5×10⁵
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10⁹。

我们可以对比发现，节点n的取值变大了，那么按照之前的时间复杂度O(n²)是肯定会超时的，所以我们需要降低时间复杂度，使用优先队列（小根堆）解决，并且随着n的取值变大，我们使用领接表来替代邻接矩阵存储图之间的关系

第一题：找到未标记的离源点最近的点 O(n²)

   for(int i = 0 ; i < n ; i ++ ){ 
            int t = -1; //t这个变量,准备来说就是转折用的
            for(int j = 1 ; j <= n ; j ++ ){
                /***
                 * 因为数字是大于1的，所以从1开始遍历寻找每个数
                 * 如果s集合中没有这个数
                 * 并且t == -1，表示刚开始 或者 后面的数比我心找的数距离起点的距离短
                 * 然后将j 的值赋值给 t
                 ***/
                if(!st[j] && (t == -1 || dist[j] < dist[t])){
                    t = j; 
                }
            }
            
1
2
3
4
5
6
7
8
9
10
11
12
13
14

算法的主要耗时的步骤是从dist 数组中选出：没有确定最短路径的节点中距离源点最近的点 t。只是找个最小值而已，没有必要每次遍历一遍dist数组。在一组数中每次能很快的找到最小值，很容易想到使用优先队列（小根堆）

代码实现

import java.util.*;
class PIIs implements Comparable{
    private int first;//距离值
    private int second;//点编号

    public int getFirst()
    {
        return this.first;
    }
    public int getSecond()
    {
        return this.second;
    }
    public PIIs(int first,int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(first, o.first);
    }
}
public class Main{
    static int N = 150010,n,m,idx,max = 0x3f3f3f3f;
    static int [] h = new int[N],e = new int[N],ne = new int[N],w = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    public static void add(int a,int b,int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static int dijkstra()
    {
        //优先队列，保证每次取出都是最小值
        //维护当前未在st中标记过且离源点最近的点   小跟堆
        PriorityQueue queue = new PriorityQueue();
        Arrays.fill(dist, max);
        dist[1] = 0;
        queue.add(new PIIs(0,1));
        while(!queue.isEmpty())
        {
            //1、找到当前未在s中出现过且离源点最近的点
            PIIs p = queue.poll();
            int distance = p.getFirst();
            int t = p.getSecond();
            if(st[t]) continue;
            //2、将该点进行标记
            st[t] = true;
            //3、用t更新其他点的距离
            for(int i = h[t];i != -1;i = ne[i])//不要被这个遍历误导，这只是一个遍历循环而已，i只是下一个点的下标
            {
                int j = e[i];// i只是个下标，e中在存的是i这个下标对应的点和值。
                if(dist[j] > distance + w[i])
                {
                    dist[j] = distance + w[i];
                    queue.add(new PIIs(dist[j],j));
                }
            }

        }
        if(dist[n] == max) return -1;
        return dist[n];
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        Arrays.fill(h,-1);
        while(m -- > 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            add(a,b,c);
        }
        int res = dijkstra();
        System.out.println(res);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

总结

迪杰斯特拉算法适用于求正权有向图中，源点到其余各个节点的最短路径。注意：图中可以有环，但不能有负权边。

例如：如下图就不能使用迪杰斯特拉算法求节点 1 到其余各个节点的最短距离。