刷题日志--最短路问题 5.22

更新日志

5.23

更新了堆优化的Dijkstra写法

5.22

动脑子好累吖，想打游戏，Apex的KD都1.07了

Heat Wave G

来源：洛谷
链接：https://www.luogu.com.cn/problem/P1339

题目描述

有一个 n 个点 m 条边的无向图，请求出从 s 到 t 的最短路长度。

输入格式

第一行四个正整数 n,m,s,t。
接下来 m 行，每行三个正整数 u,v,w，表示一条连接 u,v，长为 w 的边。

输出格式

输出一行一个整数，表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 100% 的数据，1 ≤ n ≤ 2500，1 ≤ m ≤ 6200，1 ≤ w ≤ 1000。

【样例说明】
5 -> 6 -> 1 -> 4 为最短路，长度为 3+1+3 = 7。

分析

Dijkstra算法的核心是贪心，适用场景是解决单源最短路问题，即一个点到其他所有点的距离。~~数据结构里讲过，但是我忘了~~
它先求出一条长度最短的路径，再参照这条长度最短的路径，求出一条长度次短的路径，直至求出所有点到源点的最短路径。
朴素版的Dijkstra算法比较适用于稠密图（当然稀疏图也能做）

对于本题，我们先创建一个二维数组当邻接矩阵，用来存储两点之间的距离，例：map[i][j]表示从i到j有一条长为map[i][j]的边。先将map中的元素全部初始化为0x3f3f3f3f（一个很大的数，10^9级，一般可以用来当做最大值），随后读入数据，由于可能存在重边，所以我们只需要取最小的边即可。本题是无向图，所以我们需要把两个方向都初始化一下。
之后创建一个一维数组value，用来存储其他点到源点的距离，同样初始化为0x3f3f3f3f，源点到源点的距离初始化为0，之后就是我们的Dijkstra算法了，最外层循环迭代n次，求出所有点到源点的距离，内层循环找当前长度最短的路径，用完之后把它加入到used中。之后用这条最短路径，去更新次短路径，迭代n次之后就求完了所有点到源点的最短路径了。

Code

当然也可以把Dijkstra算法封装成一个函数

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

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int s = scan.nextInt();
        int t = scan.nextInt();
        int[][] map = new int[n + 1][n + 1];
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(map[i], 0x3f3f3f3f);
        }
        while (m-- > 0) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            map[a][b] = map[b][a] = Math.min(map[a][b], c);
        }
        boolean[] used = new boolean[n + 1];
        int[] value = new int[n + 1];
        Arrays.fill(value, 0x3f3f3f3f);
        value[s] = 0;
        for (int i = 0; i < n; i++) {
            int minIndex = -1;
            for (int j = 1; j <= n; j++) {
                if (!used[j] && (minIndex == -1 || value[j] < value[minIndex]))
                    minIndex = j;
            }
            used[minIndex] = true;
            for (int j = 1; j <= n; j++) {
                value[j] = Math.min(value[j], value[minIndex] + map[minIndex][j]);
            }
        }
        System.out.println(value[t]);
    }
}

单源最短路

来源：牛客
链接：戳这里

问题叙述

描述
在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径，返回 1 到 n 的最短路径值。如果 1 无法到 n ，输出 -1

图中可能有重边，无自环。

数据范围：1 < n ≤ 50， 1 ≤ m ≤ 5000，1 ≤ dist(n,m) ≤ 1000

示例1
输入：
5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]
返回值：
9

示例2
输入：
2,1,[[1,2,4]]
返回值：
4

备注：
两个整数n和m,表示图的顶点数和边数。
一个二维数组，一维3个数据，表示顶点到另外一个顶点的边长度是多少
每条边的长度范围[0,1000]。
注意数据中可能有重边

分析

Code

import java.util.*;

public class Solution {
    public static int findShortestPath(int n, int m, int[][] graph) {
        int[][] map = new int[n + 1][n + 1];
        int[] dist = new int[n + 1];
        boolean[] used = new boolean[n + 1];
        for (int i = 0; i < n + 1; i++)
            Arrays.fill(map[i], 0x3f3f3f3f);
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        for (int[] g : graph) {
            int a = g[0], b = g[1], c = g[2];
            map[a][b] = Math.min(map[a][b], c);
        }
        //Dijkstra
        for (int i = 0; i < n; i++) {
            int minIndex = -1;
            for (int j = 1; j <= n; j++) {
                if (!used[j] && (minIndex == -1 || dist[j] < dist[minIndex]))
                    minIndex = j;
            }
            used[minIndex] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[minIndex] + map[minIndex][j]);
            }
        }
        return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
    }
}

import java.util.*;

public class Solution {
    public static int findShortestPath(int n, int m, int[][] graph) {
        int[][] map = new int[n + 1][n + 1];
        for (int i = 0; i < n + 1; i++)
            Arrays.fill(map[i], 0x3f3f3f3f);
        for (int[] g : graph) {
            int a = g[0], b = g[1], c = g[2];
            map[a][b] = Math.min(map[a][b], c);
        }
        //Floyd
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);
                }
            }
        }
        return map[1][n] == 0x3f3f3f3f ? -1 : map[1][n];
    }
}

import java.util.*;

public class Solution {
    int N = 510, M = 5010;
    int n, m, index;
    int[] head = new int[N], value = new int[M], next = new int[M], weight = new int[M];
    int[] dist = new int[N];
    boolean[] vis = new boolean[N];

    void add(int a, int b, int c) {
        value[index] = b;
        next[index] = head[a];
        head[a] = index;
        weight[index] = c;
        index++;
    }

    public int findShortestPath(int _n, int _m, int[][] graph) {
        n = _n;
        m = _m;
        Arrays.fill(head, -1);
        for (int[] g : graph) {
            int s = g[0], u = g[1], v = g[2];
            add(s, u, v);
        }
        dijkstra();
        return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
    }

    void dijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        q.add(new int[]{1, 0});
        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            int id = tmp[0];
            if (vis[id]) continue;
            for (int i = head[id]; i != -1; i = next[i]) {
                int j = value[i];
                if (dist[j] > dist[id] + weight[i]) {
                    dist[j] = dist[id] + weight[i];
                    q.add(new int[]{j, dist[j]});
                }
            }
        }
    }
}