最短路题单 - 1

floyed

题目:. - 力扣（LeetCode）

AC代码：

class Solution {
    int[][] g;
    
    public int networkDelayTime(int[][] times, int n, int k) {
        g = new int[n + 1][n + 1];
​
        for(int i = 0;i<=n;i++){
            for(int j = 0;j<=n;j++){
                if(i == j) g[i][j] = 0;
                else g[i][j] = 0x3f3f3f3f;
            }
        }
​
        for(var t : times){
            int a = t[0], b = t[1], w = t[2];
            g[a][b] = Math.min(g[a][b],w);
            // g[b][a] = Math.min(g[b][a],w);
        }
        // floyed 
        for(int p = 1;p<=n;p++){
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=n;j++){
                    g[i][j] = Math.min(g[i][j],g[i][p] + g[p][j]);
                }
            }
        }
        int res = 0;
        for(int i = 1;i<=n;i++){
            res = Math.max(res,g[k][i]);
        }
        if(res == 0x3f3f3f3f) return -1;
        return res;
    }
}

Dijkstra

题目：. - 力扣（LeetCode）

AC代码：

堆优化-邻接表版

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        double[] dist = new double[n];
        List<double[]>[] g = new ArrayList[n];
        Arrays.setAll(g,e -> new ArrayList<>());
        boolean[] st = new boolean[n];
        Arrays.fill(dist,0);
​
        int m = edges.length;
        for(int i = 0;i<m;i++){
            var t = edges[i];
            g[t[0]].add(new double[]{t[1],succProb[i]});
            g[t[1]].add(new double[]{t[0],succProb[i]});
        }
        
        PriorityQueue<double[]> heap = new PriorityQueue<>((a,b) ->Double.compare(a[0], b[0]));
        heap.add(new double[]{start_node,1});
        dist[start_node] = 1;
​
        while(!heap.isEmpty()){
            var p = heap.poll();
            int u = (int)p[0];
            double t = p[1];
            if(t < dist[u]) continue;
​
            for(var ne : g[u]){
                int v = (int)ne[0];
                double c = ne[1];
                if(c * t > dist[v]){
                    dist[v] = c * t;
                    heap.offer(new double[]{v,c * t});
                }
            }
        }
        return dist[end_node];
    }
}

朴素-邻接矩阵版

但是注意这里这样得话会发生超出内存限制得错误,g 临界矩阵的所需内存太大了。

class Solution {
    double[] dist;  // 记录从 start到其他点的概率
    double[][] g;
    boolean[] st;
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        dist = new double[n];
        g = new double[n][n];
        st = new boolean[n];
        Arrays.fill(dist,0);
        // for(var t :g){
        //     for(int i = 0;i<t.length;i++)
        //         t[i] = (double)0;
        // }
​
        int m = edges.length;
        for(int i = 0;i<m;i++){
            var t = edges[i];
            g[t[0]][t[1]] = succProb[i];
            g[t[1]][t[0]] = succProb[i];
        }
        for(int i = 0;i<n;i++) dist[i] = g[start_node][i];
        dijkstra(n,start_node,end_node);
        return dist[end_node];
​
    }
    // dijkstra 计算 从start 到 end 最大概率
    public void dijkstra(int n, int start,int end){
        dist[start] = 1;
        st[start] = true;
        // 寻找最大概率
        for(int i = 1;i<n;i++){
            int t = -1;
            for(int j = 0;j<n;j++){
                if(!st[j] && (t == -1 || dist[j] > dist[t]))
                    t = j;
            }        
            // 更新其他点
            for(int j = 0;j<n;j++){
                dist[j] = Math.max(dist[j],dist[t] * g[t][j]);
            }
            st[t] = true;
        }
    }
}

题目：. - 力扣（LeetCode）

Graph 图

addEdge为新增加权边

shortestPath 计算start到end的最小路径长度

class Graph {
    private static final int INF = Integer.MAX_VALUE / 2; // 防止更新最短路时加法溢出
​
    private int[][] g;
​
    public Graph(int n, int[][] edges) {
        g = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
        for (int i = 0; i < n; ++i)
            Arrays.fill(g[i], INF);
        for (var e : edges)
            g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边）
    }
​
    public void addEdge(int[] e) {
        g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证这条边之前不存在）
    }
​
    // 朴素 Dijkstra 算法
    public int shortestPath(int start, int end) {
        int n = g.length;
        var dis = new int[n]; // 从 start 出发，到各个点的最短路，如果不存在则为无穷大
        Arrays.fill(dis, INF);
        dis[start] = 0;
        var vis = new boolean[n];
        for (;;) {
            // 找到当前最短路，去更新它的邻居的最短路
            // 根据数学归纳法，dis[x] 一定是最短路长度
            int x = -1;
            for (int i = 0; i < n; ++i)
                if (!vis[i] && (x < 0 || dis[i] < dis[x]))
                    x = i;
            if (x < 0 || dis[x] == INF) // 所有从 start 能到达的点都被更新了
                return -1;
            if (x == end) // 找到终点，提前退出
                return dis[x];
            vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
            for (int y = 0; y < n; ++y)
                dis[y] = Math.min(dis[y], dis[x] + g[x][y]); // 更新最短路长度
        }
    }
}