算法学习-最短路模板（JAVA实现）

本文最后更新于：April 6, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

注意：无特殊说明，则n表示点的个数，m表示边的条数。

单源最短路

某一个点到其他点的最短距离。

不存在负边

朴素Dijkstra算法

适合稠密图（点少边多）。常用邻接矩阵存图。时间复杂度：O(n2)

练习题目：849. Dijkstra求最短路 I

上面的题目已经要收费才能做了，重新给一个其他题目练习。 Dijkstra求最短路

下面实现的代码都是之前的那个题目的AC代码，现在题目不能用了，就仅仅参考吧！思路都是一样的。

邻接矩阵实现
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 1000+7;
    public static int INF = 0x3f3f3f3f;
    public static int[] dis = new int[maxd];
    public static int[][] g = new int[maxd][maxd];
    public static boolean[] vis= new boolean[maxd];

    public static long Dijkstra(int n){
        for(int i=1;i<=n;++i) dis[i] = INF;
        dis[1] = 0;
        for(int i=1;i<=n;++i){ //n次遍历
            int t = -1;
            for(int j=1;j<=n;++j){ //每一次都找距离最短的,类似于选择排序中每次都找最大或最小的下标进行交换
                if( !vis[j] && ( t==-1 || dis[t]>dis[j] ) ) {
                    t = j;
                }
            }
            vis[t] = true; //放进已知最短距离的集合中
            for(int j=1;j<=n;++j){ //更新与该点(t点)有边的点的距离
                dis[j] = Math.min(dis[j],dis[t]+g[t][j]);
            }
        }
        if(dis[n]==INF) return -1;
        else return dis[n];
    }


    public static void main(String[] args) throws Exception {

        int n = nextInt(); //n个点，m条边
        int m = nextInt();
        for(int i=1;i<=n;++i){ //初始化
            for(int j=1;j<=n;++j){
                g[i][j] = INF;
            }
        }
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            g[a][b]=Math.min(g[a][b],c); //防止重边
        }
        cout.println(Dijkstra(n));
        cout.flush();
        
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

链式前向星实现
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 100000+7;
    public static int INF = 0x3f3f3f3f;

    public static class Edge{
        private int pre;
        private int w;
        private int to;

        public void setPre(int pre) {
            this.pre = pre;
        }

        public void setW(int w) {
            this.w = w;
        }

        public void setTo(int to) {
            this.to = to;
        }

        public int getPre() {
            return pre;
        }

        public int getW() {
            return w;
        }

        public int getTo() {
            return to;
        }
    }
    public static Edge[] edge = new Edge[maxd];
    public static int[] head = new int[maxd];
    public static int[] dis = new int[maxd];
    public static boolean[] vis= new boolean[maxd];
    public static int node = 0;
    //初始化
    public static void init(int n,int m){
        for(int i=0;i<=m;++i) {
            edge[i] = new Edge();
        }
        for(int i=1;i<=n;++i) {
            head[i]=-1;
        }
        node=0;
    }
    public static void add_edge(int a,int b,int c){
        edge[node].setTo(b);
        edge[node].setW(c);
        edge[node].setPre(head[a]);
        head[a]=node++;
    }

    public static long Dijkstra(int n){
        for(int i=1;i<=n;++i) dis[i] = INF;
        dis[1] = 0;
        for(int i=1;i<=n;++i){ //n次遍历
            int t = -1;
            for(int j=1;j<=n;++j){ //每一次都找距离最短的,类似于选择排序中每次都找最大或最小的下标进行交换
                if( !vis[j] && ( t==-1 || dis[t]>dis[j] ) ) {
                    t = j;
                }
            }
            vis[t] = true; //放进已知最短距离的集合中
            for(int j=head[t];j!=-1;j=edge[j].getPre()){
                int to = edge[j].getTo();
                dis[to]=Math.min(dis[to],dis[t]+edge[j].getW());
            }
        }
        if(dis[n]==INF) return -1;
        else return dis[n];
    }


    public static void main(String[] args) throws Exception {

        int n = nextInt(); //n个点，m条边
        int m = nextInt();
        init(n,m);
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            add_edge(a,b,c);
        }
        cout.println(Dijkstra(n));
        cout.flush();

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

堆优化Dijkstra算法

适合稀疏图（点多边少）。时间复杂度：O(m*logn)

练习题目：850. Dijkstra求最短路 II 。同样，重新再给一个练习题目 Dijkstra求最短路 

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int[] head = new int[maxd]; //此点的最后一条有关联的边的编号
    public static int[] edgePre = new int[maxd]; // 上一条边的编号
    public static int[] edgeW = new int[maxd]; //边的权重
    public static int[] edgeTo = new int[maxd]; //此条边的终点
    public static int[] dis = new int[maxd]; //此点到起点的最短距离
    public static boolean[] vis= new boolean[maxd]; //是否访问过
    public static int node = 0; //边的编号
    public static class Edge implements Comparable<Edge> {
        private int to; //点
        private int w; //此点到起点的最短距离
        Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
        public int compareTo(Edge obj) {
            return this.w - obj.w;
        }
    }
    //初始化
    public static void init(int n,int m){ //n个点，m条边
        for(int i=1;i<=n;++i) {
            head[i]=-1;
            dis[i]=INF;
            vis[i]=false;
        }
        node=0;
    }
    public static void add_edge(int a,int b,int c){ //a到b的权值为c
        edgeTo[node]=b;
        edgeW[node]=c;
        edgePre[node]=head[a];
        head[a]=node++;
    }
    public static void Dijkstra(int start,int end){
        PriorityQueue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(start,0));
        dis[start] = 0;
        while(!q.isEmpty()) {
            int u = q.poll().to;
            if(vis[u] == true) continue;
            vis[u] = true;
            for(int i = head[u]; i!=-1; i=edgePre[i]) {
                int to = edgeTo[i];
                if(dis[to] > dis[u] + edgeW[i]) {
                    dis[to] = dis[u] + edgeW[i];
                    q.add(new Edge(to, dis[to]));
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {

        int n = nextInt(); //n个点，m条边
        int m = nextInt();
        init(n,m);
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            add_edge(a,b,c); //可以用于重边不同权的情况
        }
        Dijkstra(1,n);
        cout.println(dis[n]==INF? -1:dis[n]);
        cout.flush();

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

存在负边

SPFA

可以判断是否存在环。时间复杂度：O(m)（一般情况），最坏情况O(n*m)。不论边权是正的还是负的，都可以做。算法平均时间复杂度是 O(km)，k 是常数。

添加一个练习题目 可参考下面代码。

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
public static int maxd = 100000+7;
public static int INF = 0x3f3f3f3f;
public static int[] dis = new int[maxd];
public static int[] head = new int[maxd];
public static int[] edgePre = new int[maxd]; // 上一条边的编号
public static int[] edgeW = new int[maxd]; //边的权重
public static int[] edgeTo = new int[maxd]; //此条边的终点
public static int[] num = new int[maxd]; //此条边的终点
public static boolean[] vis = new boolean[maxd];
public static int node = 0;

//初始化
public static void init(int n,int m){ //n个点，m条边
  for(int i=1;i<=n;++i) {
    head[i]=-1;
    dis[i]=INF;
    vis[i]=false;
  }
  node=0;
}
public static void add_edge(int a,int b,int c){ //a到b的权值为c
  edgeTo[node]=b;
  edgeW[node]=c;
  edgePre[node]=head[a];
  head[a]=node++;
}

public static boolean SPFA(int end){
  Queue<Integer> q = new LinkedList<Integer>();
  q.add(1);
  dis[1]=0;
  num[1]=1;
  vis[1]=true;
  while (!q.isEmpty()){
    int u = q.poll();
    vis[u]=false;
    for(int i = head[u];i!=-1;i=edgePre[i]){
      int v = edgeTo[i];
      if(dis[v]<=dis[u]+edgeW[i]) continue;
      dis[v]=dis[u]+edgeW[i];
      num[v]=num[u]+1;
      if(num[v]>end){ //如果存在某个顶点是由n条边能得到，则有负权路径
        return true;
      }
      if (!vis[v]){
        vis[v] = true;
        q.add(v);
      }
    }
  }
  return false;
}

多源最短路

Floyd

可以求任意两点间的最短距离。时间复杂度：O(n3)。一种动态规划算法，稠密图效果最佳，边权可正可负。

练习题目：849. Dijkstra求最短路 I 。重新添加一个题目 Dijkstra求最短路 

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
85
86
87
88
89
90
91
92
93
94
95
96
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    //    cin.ordinaryChars('0', '9') ;
    //    cin.wordChars('0', '9');
    //    Arrays.sort(a, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]); //升序

    public static int maxd = 1000+7;
    public static int INF = 0x3f3f3f3f;
    public static int[][] dp = new int[maxd][maxd];
    
    public static void floyd(int n){
        for(int k=1;k<=n;++k){
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    if(dp[i][j]>dp[i][k]+dp[k][j]){
                        dp[i][j]=dp[i][k]+dp[k][j];
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        int n = nextInt();
        int m = nextInt();
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                dp[i][j]=INF;
            }
        }
        while(m-->0){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            dp[a][b] = Math.min(dp[a][b],c);
        }
        floyd(n);
        cout.println(dp[1][n]==INF? -1:dp[1][n]);
        cout.flush();

        closeAll();
    }
    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }

    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }

    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }

    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}