力扣-最短路

这里介绍三种算法，包括适用于稀疏图与边关系密切且能处理负权的BellmanFord算法，适用于稠密图的和顶点关系密切且能处理负权边的Floyd算法，以及采用贪心策略适用于稠密图和顶点关系密切不能处理负权边的Dijkstra算法

TIPS： Floyd算法虽然能处理负权边但是不能解决带有“负权回路”(负权环)，因为带有负权回路的图没有最短路径，因为总能找到比当前最小值更小的路径。因此最大路径也就不存在

网络延迟时间

我的题解：

思路:本题三种算法都可采用

1.Floyd算法(邻接矩阵)：核心是要求两个点的最短距离，可以尝试用第三个点进行周转，看能否在周转后是的这两个点的距离更短，若可以我们就更新当前这两个点的最短路径

class Solution {
    int INF = 0x3f3f3f3f;
    int n;
    int[][] arr;
    public int networkDelayTime(int[][] times, int _n, int k) {
        n = _n + 1;
        arr = new int[n][n];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                arr[i][j] = arr[j][i] = i == j ? 0 : INF;
            }
        }

        for(int[] cur : times){
            arr[cur[0]][cur[1]] = cur[2];
        }
        floyd(arr);
        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(arr[k][i], max);
        }
        return max == INF ? -1 : max;
    }
	//Floyd核心语句
    void floyd(int[][] arr){
        for (int k = 1; k < n; k++) {
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
                }
            }
        }
    }
}

2.Dijkstra算法(邻接矩阵)：核心思想是通过边来松弛一号顶带你到其他顶点的距离，采用贪心策略，每次都选择一个未访问的点，离1号顶点最近的点，来进行松弛操作。单源最短路径

class Solution {
 int K = 110, N = 110;
    int[][] w = new int[N][N];
    boolean[] vis = new boolean[N];
    int[] dis = new int[N];
    int inf = 0x3f3f3f3f;

    /**
     * dijkstra 核心思想是通过边来松弛一号顶点到其他各顶点的距离
     * @param times
     * @param _n
     * @param _k
     * @return
     */
    public int networkDelayTime(int[][] times, int _n, int _k) {
        int n = _n + 1;
        int k = _k;
        //初始化邻接矩阵，主对角线上为0，其它为无穷
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                w[i][j] = w[j][i] = i == j ? 0 : inf;
            }
        }
		//用times进一步初始化边的权值
        for(int[] i : times){
            w[i[0]][i[1]] = i[2];
        }
		//初始化dis，k节点未0，其他为inf
        Arrays.fill(dis, inf);
        dis[k] = 0;
        //Dijkstra核心语句
        for (int i = 1; i < n; i++) {
            int t = 0, min = inf;
            //每次都选择一个离一号节点最近的点
            for (int j = 1; j < n; j++) {
                if(!vis[j] && min > dis[j]) {
                    min = dis[j];
                    t = j;
                }
            }
            //标记为已访问
            vis[t] = true;
            //用该点的边去松弛1号顶点到其它顶点的距离
            for(int j = 1; j < n; j++){
                if(dis[j] > dis[t] + w[t][j]){
                    dis[j] = dis[t] + w[t][j];
                }
            }
        }
		//若1号顶点到其它顶点存在有效路径，那么就返回这些路径中的最大值
        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, dis[i]);
        }
        return max > inf / 2 ? -1 : max;
    }
}

3.**Dijkstra + 最小堆算法：**这里用最小堆进行优化每次选取一个

class Solution {
 int K = 110, N = 110;
    int[][] w = new int[N][N];
    int[] dis = new int[N];
    int inf = 0x3f3f3f3f;

    /**
     * dijkstra 核心思想是通过边来松弛一号顶点到其他各顶点的距离
     * @param times
     * @param _n
     * @param _k
     * @return
     */
    public int networkDelayTime(int[][] times, int _n, int _k) {
        int n = _n + 1;
        int k = _k;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                w[i][j] = w[j][i] = i == j ? 0 : inf;
            }
        }

        for(int[] i : times){
            w[i[0]][i[1]] = i[2];
        }

        Arrays.fill(dis, inf);
		//核心语句
        //最小堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        dis[k] = 0;
        //将k号节点加入最小堆中
        priorityQueue.add(k);
		//当队列不为空，就弹出当前节点
        while(!priorityQueue.isEmpty()){
            int t = priorityQueue.poll();
            //松弛操作
            //枚举每一个节点
            for (int j = 1; j < n; j++) {
                //若t -> j之间存在边，使得dis[j] > dis[t] + w[t][j],我们就更新原点到j点的最短路径,并将该点加入队列中
                if(w[t][j] < inf / 2 && dis[j] > dis[t] + w[t][j]){
                    dis[j] = dis[t] + w[t][j];
                    priorityQueue.add(j);
                }
            }
        }
        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, dis[i]);
        }
        return max > inf / 2 ? -1 : max;
    }
}

4.BellmanFord算法:对所有边进行n-1次松弛操作

class Solution {
   int N = 110, M = 6010;
    int inf = -1;
    int[] u = new int[M], v = new int[M], w = new int[M];
    int[] dis = new int[N];
    public int networkDelayTime(int[][] ts, int _n, int _k) {
       int m = ts.length;
       int n = _n;
       int k = _k;
        for (int i = 1; i <= m; i++) {
            u[i] = ts[i - 1][0];
            v[i] = ts[i - 1][1];
            w[i] = ts[i - 1][2];
        }

        Arrays.fill(dis, inf);
        dis[k] = 0;
		//核心语句
        for (int i = 1; i < n; i++) {
            //枚举每条边
            for (int j = 1; j <= m; j++) {
                //若当前原点到u[j]存在边
               if(dis[u[j]] != inf){
                   //若原点到v[j]的距离以前不存在路径，我们就通过中间节点u[j]对v[j]到原点的距离进行松弛操作
                   if(dis[v[j]] == inf){
                       dis[v[j]] = dis[u[j]] + w[j];
                       //若存在路径，且松弛后的路径更短，就更新原点到v[j]的最短距离
                   }else{
                       dis[v[j]] = Math.min(dis[v[j]], dis[u[j]] + w[j]);
                   }
               }
            }
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            if(dis[i] == inf) return -1;
            max = Math.max(dis[i], max);
        }
        return max;
    }
}

5.BellmanFord算法 + 队列：这里可以用队列优化的原因是，若当前节点不在队列中，且通过本次松弛操作使得原点到目标节点的距离变短(可达)，则我们将当前节点加入队列中。这里实现时，我们可以用一个长度为n的名为vis的boolean类型数组进行标记当前节点是否在队列中，初始化时我们将节点k加入队列中，并标记vis[k] = true,在弹出时我们将vis[k]重新置为false，在松弛操作有效时，我们先判断vis[i]是否为false若时，我们就将节点i加入队列中

class Solution {
   /**
     * spfa算法
     * @param times
     * @param n
     * @param k
     * @return
     */
    int N = 110, M = 6010, inf = 0x3f3f3f3f;
    int[] dis = new int[N];
    boolean[] vis = new boolean[N];
    int[][] w = new int[N][N];
    int n, k, m;
    public int networkDelayTime(int[][] times, int _n, int _k) {
        m = times.length;
        n = _n;
        k = _k;
        //构图
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n ; j++) {
                w[i][j] = w[j][i] = i == j ? 0 : inf;
            }
        }
        for (int i = 0; i < m; i++) {
          w[times[i][0]][times[i][1]] = times[i][2];
        }
        spfa();
       	//获取最大值
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dis[i]);
        }
        return max > inf / 2 ? -1 : max;
    }
	//核心语句
    void spfa(){
        //初始化dis
        Arrays.fill(dis, inf);
        //标记原点，并将原点标记为已访问，加入队列中
        dis[k] = 0;
        vis[k] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(k);
        while(!queue.isEmpty()){
            int t = queue.poll();
            vis[t] = false;
            //枚举该点的每条边
            for (int i = 1; i <= n; i++) {
                //若原点和t节点之间边，且t节点到i节点之间存在边，且本次更新能使得原点到dis[i]之间的路径变短，我们就进行松弛操作
                if(dis[t] < inf / 2 && w[t][i] < inf / 2 && dis[i] > dis[t] + w[t][i]){
                    dis[i] = dis[t] + w[t][i];
                    //若节点i不在队列中，我们就将节点i加入队列
                    if(!vis[i]){
                        queue.offer(i);
                        vis[i] = true;
                    }
                }
            }
        }
    }
}

787. K 站中转内最便宜的航班

我的题解：

思路:该题的思路可以是动态规划或者是使用BellmanFord算法

1.动态规划，第i个城市只能从第j个城市转移而来，而转移的次数t只能从t-1次转移而来

class Solution {
int INF = 100000, N = 110;
    int[][] dp = new int[N][N];

    /**
     * 状态转移方程：dp[t][i] = min(dp[t][i], dp[t-1][j] + cost)
     * 边界条件:dp[0][src] = 0
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int t = k + 1;
        for (int i = 0; i <= t; i++) {
            Arrays.fill(dp[i], INF);
        }
        //边界条件
        dp[0][src] = 0;
        //状态转移
        for (int c = 1; c <= t; c++) {
            for (int[] flight : flights) {
                int i = flight[1], j = flight[0], cost = flight[2];
                dp[c][i] = Math.min(dp[c][i], dp[c - 1][j] + cost);
            }
        }

        int min = INF;
        for (int i = 0; i <= t; i++) {
            min = Math.min(min, dp[i][dst]);
        }
        return min == INF ? -1 : min;
    }

}

2.BellmanFord + 邻接矩阵

class Solution {
   int N = 110, INF = 0x3f3f3f3f;
    int[][] g = new int[N][N];
    int[] dis = new int[N];

    /**
     * BellmanFord
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = g[j][i] = i == j ? 0 : INF;
            }
        }

        for(int[] flight : flights){
            int u = flight[0], v = flight[1], w = flight[2];
            g[u][v] = w;
        }
        //t从0 ~ k次一共k+1次，代表从1 ~ k+1,i起始点，j终点，通过从i~j这条边不断对从src到j的路径进行松弛操作
        Arrays.fill(dis, INF);
        dis[src] = 0;
        //外层控制松弛的次数
        for (int t = 0; t < k + 1; t++) {
           	//这里确保每次循环只会松弛一次
            int[] c = dis.clone();
            //若存在i -> j的路径且存在src到i的路径，且松弛后路径更短就进行松弛
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dis[j] = Math.min(dis[j], c[i] + g[i][j]);
                }
            }
        }
        return dis[dst] == INF ? -1 : dis[dst];
    }
}

3.BellmanFord(推荐)

class Solution {
     int N = 110, INF = 0x3f3f3f3f;
    int[] dis = new int[N];

    /**
     * 不使用邻接矩阵或邻接表，这里直接使用flights中的边对dis从0~n的路径进行松弛操作,BellManFord算法的外层循环就是中转的次数
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Arrays.fill(dis, INF);
        dis[src] = 0;
        //外层控制松弛的次数
        for (int i = 0; i < k + 1; i++) {
            //这里确保每次只松弛一次，同一层不会松弛多次
            int[] c = dis.clone();
            for (int[] flight : flights) {
                int u = flight[0], v = flight[1], w = flight[2];
                dis[v] = Math.min(dis[v], c[u] + w);
            }
        }
        return dis[dst] > INF / 2 ? -1 : dis[dst];
    }
}

1928. 规定时间内到达终点的最小花费

我的题解：

思路:本题有两个约束，时间约束和最短路径约束，可以用动态规划来解决，特别需要注意的是这里因为路径是无向的，因此需要双向状态转移

动态规划问题的核心是找出边界条件和状态转移方程
边界条件:
$d p [i] [j] = p a ss in g F ees [0] (i = 0, j = 0)$

$d p [i] [j] = I NF (i! = 0 ， j! = 0)$

状态转移方程:
$d p [t] [i] = min (d p [t] [i], d p [t - w] [j] + p a ss in g F ees [i]) (t >= w)$

$d p [t] [j] = min (d p [t] [j], d p [t - w] [i] + p a ss in g F ees [j]) (t >= w)$
```
class Solution {
   int INF = 0x3f3f3f3f;
    int T = 1010, N = 1010;
    int[][] dp = new int[T][N];

    /**
     * 边界条件:dp[0][0] = passingFees[0]
     * 状态转移方程:dp[t][j] = min(dp[t][j], dp[t - w][i] + passingFees[j])
     * dp[t][i] = min(dp[t][i], dp[t - w][j] + passingFees[i])
     * @param maxTime
     * @param edges
     * @param passingFees
     * @return
     */
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        for (int i = 0; i <= maxTime; i++) {
            Arrays.fill(dp[i], INF);
        }
        //边界条件
        dp[0][0] = passingFees[0];
        //状态转移
        for (int t = 1; t <= maxTime; t++) {
            for(int[] edge : edges){
                int i = edge[0], j = edge[1], w = edge[2];
                //双向
                if(t - w >= 0){
                    dp[t][i] = Math.min(dp[t][i], dp[t - w][j] + passingFees[i]);
                    dp[t][j] = Math.min(dp[t][j], dp[t - w][i] + passingFees[j]);
                }
            }
        }

        int min = INF;
        for (int t = 1; t <= maxTime; t++) {
            min = Math.min(min, dp[t][n - 1]);
        }
        return min > INF / 2 ? -1 : min;
    }
}
```

1334. 阈值距离内邻居最少的城市

我的题解：

思路:多源最短路径考虑用floyd算法解决,时间复杂度O(N^{3),空间复杂度O(N}2)

//初始化参数
    int N = 110, INF = 0x3f3f3f3f;
    int[][] g = new int[N][N];
    int[] counts = new int[N];
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        //构图
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], INF);//不存在自己到自己的边
        }
        for(int[] edge : edges){
            int u = edge[0], v = edge[1], w = edge[2];
            g[u][v] = g[v][u] = w;//无向图双向赋值
        }
        //floyd算法
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(j != i && g[i][k] < INF / 2 && g[k][j] < INF / 2 && g[i][k] + g[k][j] < g[i][j]){//不存在环，因此i，j不能相同
                        g[i][j] = g[i][k] + g[k][j];
                    }
                }
            }
        }

        //对小于distance的边进行计数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(g[i][j] <= distanceThreshold) counts[i]++;
            }
        }
        //找出点最少的边，且索引最大
        int idx = 0, min = INF;
        for (int i = 0; i < n; i++) {
            if(counts[i] <= min){
                min = counts[i];
                idx = i;
            }
            
        }
        return idx;
    }

1368. 使网格图至少有一条有效路径的最小代价

我的题解：

思路:可以将每个格子看成一个点，对于一个点与它相邻的点有一条无向边相连，其中grid(i)(j)中的数字从1~4对应着四个方向，若与扩展的方向相同则该边的权重为0，反之为1，这样一来该题同样可以看成最短路径问题(单源最短路径)。

在这里介绍两种方法：dijsktra算法和0-1BFS算法

dijkstra的核心思路是每一次取一个离原点最近且未访问的点，用该点的边对原点到其它的的距离进行松弛操作，使得原点到其它点的距离从不可达变为可达或距离缩短(开销变小)

0-1BFS的核心思路是若此次松弛有效(使得原点到其它点的距离从不可达变为可达或距离缩短(开销变小))，且边的权值只存在两种可能0或1，那么将权值为0的加到双向队列的头结点前，若为1则加到双向队列的尾结点后

1.Dijkstra:

   import java.util.Arrays;
   import java.util.Comparator;
   import java.util.PriorityQueue;
   
   public class Test1 {
       int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
       final int INF = 0x3f3f3f3f;
       /**
        * 思路：最短路径(这里的最短路径指的是最小的次数),因此仍然可以使用dijkstra算法
        * 这里使用优先队列优化后的dijkstra算法
        * step1:初始化count为INF，并初始化count[0][0]为0，vis[0][0]为true,将0,0点加入优先队列中
        * step2:若优先队列不为空，就弹出队首的元素，表示离远点最近的元素，然后用该点的四个方向的边，对相邻的点到原点的距离进行松弛操作
        * step3:返回count[m-1][n-1]
        * @param grid
        * @return
        */
       public int minCost(int[][] grid) {
           //step1
           int m = grid.length, n = grid[0].length;
           int[][] count = new int[m][n];
           boolean[][] vis = new boolean[m][n];
           for (int i = 0; i < m; i++) {
               Arrays.fill(count[i], INF);
           }
           count[0][0] = 0;
           PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(Comparator.comparingInt(a -> a[1])
           );
           priorityQueue.offer(new int[] {0, 0});
           //step2
           while(!priorityQueue.isEmpty()){
               int[] cur = priorityQueue.poll();
               int x = cur[0] / n, y = cur[0] % n;
               //若该点已访问则跳过，这里同一个点可能更新多次
               if(vis[x][y]) continue;
               vis[x][y] = true;
               for (int i = 0; i < 4; i++) {
                   int nx = x + dx[i];
                   int ny = y + dy[i];
                   //路径不重复，不需要确保点未访问
                   if(nx >= 0 && nx < m && ny >= 0 && ny < n){
                       int cnt = grid[x][y] == i + 1 ? 0 : 1;
                       if(count[nx][ny] > count[x][y] + cnt){
                           count[nx][ny] = count[x][y] + cnt;
                           priorityQueue.offer(new int[] {nx * n + ny, count[nx][ny]});
                       }
                   }
               }
           }
           //step3
           return count[m - 1][n - 1];
       }
   }

2.0-1BFS

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Test2 {
    /**
     * 思路:0-1BFS
     * 步骤:
     * 1.初始化cost，将初始元素加入队列中
     * 2.当队列不为空，尝试在四个方向上进行扩展，若可以扩展，则记录此时的代价c，若此次松弛操作有效则更新扩展点的cost与此同时，根据c为0还是为1将
     * 扩展点加入队列头结点还是尾节点位置
     * 3.最后返回cost[m-1][n-1]
     * @param grid
     * @return
     */
    final int INF = 0x3f3f3f3f;
    int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
    public int minCost(int[][] grid) {
        //step1
        int m = grid.length, n = grid[0].length;
        int[][] cost = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(cost[i], INF);
        }
        cost[0][0] = 0;
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(0);
        //step2
        while(!deque.isEmpty()){
            int cur = deque.poll();
            int x = cur / n, y = cur % n;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n){
                    int c = grid[x][y] == i + 1 ? 0 : 1;
                    if(cost[nx][ny] > cost[x][y] + c){
                        cost[nx][ny] = cost[x][y] + c;
                        //核心
                        if(c == 0){
                            deque.offerFirst(nx * n + ny);
                        }else{
                            deque.offer(nx * n + ny);
                        }
                    }
                }
            }
        }
        //step3
        return cost[m - 1][n - 1];
    }
}

1514. 概率最大的路径

我的题解：

思路:本题同样是最短路的问题，可以这样考虑最短路的核心思想是找到一条最优解的路径，这里的最优解路径指的是概率最大的路径，因此我们同样可以使用单源最短路径算法Dijkstra、BellmanFord或SPFA来解决

TIPS:注意这里是无向图因此在构图的时候需要建立双向路径

1.Dijkstra + 数组

/**
     * 思路:该题同样是最短路径的思想，只不过这里的最短路径换成了最大的乘积，核心思想也是一样的，在这里INF对应的值是-1，dis[0]=1,其它为INF，单原最短路径
     * 考虑用Dijkstra算法或BellmanFord算法,这里我们用邻接表来实现
     * 步骤:
     * 1.构图，初始化dis,vis
     * 2.Dijkstra
     * 3.根据dis[end]的值返回结果
     * @param n
     * @param edges
     * @param succProb
     * @param start
     * @param end
     * @return
     */
    final int INF = -1;
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //step1
        int m = edges.length;
        double[] dis = new double[n];
        boolean[] vis = new boolean[n];
        List<List<double[]>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        //无向图双向连接
        for (int i = 0; i < m; i++) {
            int u = edges[i][0], v = edges[i][1];
            g.get(u).add(new double[] {v, succProb[i]});
            g.get(v).add(new double[] {u, succProb[i]});
        }
        Arrays.fill(dis, INF);
        dis[start] = 1d;
        //step2
        PriorityQueue<double[]> pq = new PriorityQueue<>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                if(o2[1] > o1[1]) return 1;
                else return -1;
            }
        });//这里需要每次获取一个最大的值
        pq.offer(new double[] {start, 1});
        while(!pq.isEmpty()){
            double[] cur = pq.poll();
            int u = (int) cur[0];
            if(vis[u]) continue;//若该点已访问过则跳过
            vis[u] = true;//标记该点为已访问
            for (int i = 0; i < g.get(u).size(); i++) {
                int v = (int) g.get(u).get(i)[0];
                double w = g.get(u).get(i)[1];
                if(dis[v] < dis[u] * w){//松弛操作，这里是选最大的值
                    dis[v] = dis[u] * w;
                    pq.offer(new double[]{v, dis[v]});
                }
            }
        }
        System.out.println(Arrays.toString(dis));
        //step3
        return dis[end] == -1 ? 0 : dis[end];
    }
}

2.Dijkstra + 类

class Solution {
    final int INF = -1;
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //step1
        int m = edges.length;
        double[] dis = new double[n];
        boolean[] vis = new boolean[n];
        List<List<Pair>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        //无向图双向可达
        for (int i = 0; i < m; i++) {
            int u = edges[i][0], v = edges[i][1];
            g.get(u).add(new Pair(v, succProb[i]));
            g.get(v).add(new Pair(u, succProb[i]));
        }
        Arrays.fill(dis, INF);
        dis[start] = 1;
        //step2
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>(new Comparator<Pair>() {

			@Override
			public int compare(Pair a, Pair b) {
				// TODO 自动生成的方法存根
				if(b.w > a.w) return 1;
				else return -1;
			}

			
		});//这里需要每次获取一个最大的值
        pq.offer(new Pair(start, 1));
        while(!pq.isEmpty()){
            Pair cur = pq.poll();
            int u = cur.u;
            if(vis[u]) continue;//若该点已访问过则跳过
            vis[u] = true;//标记该点为已访问
            for (int i = 0; i < g.get(u).size(); i++) {
                int v = g.get(u).get(i).u;
                double w = g.get(u).get(i).w;
                if(dis[v] < dis[u] * w){//松弛操作，这里是选最大的值
                    dis[v] = dis[u] * w;
                    pq.offer(new Pair(v, dis[v]));
                }
            }
        }
        //step3
        return dis[end] == -1 ? 0 : dis[end];
    }
    
    class Pair{
    	int u;
    	double w;
    	public Pair(int _u, double _w) {
			u = _u;
			w = _w;
		}
    }
}

3.BellmanFord + 类 (无法通过评测，只供参考)

 /**
     * BellmanFord算法
     * 无向图-最短路径-类实现
     * 步骤:
     * 1.初始化dis,vis
     * 2.调用BellmanFord算法解决，优先选择路径大的
     * 3.根据dis[end]的值决定最终的返回值
     * 提示:因为单独提供了所有边的信息，所以这里不需要构图，但是在进行松弛操作时需要双向松弛操作
     * @param n
     * @param edges
     * @param succProb
     * @param start
     * @param end
     * @return
     */
    final int INF = -1;
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //step1
        int m = edges.length;
        double[] dis = new double[n];

        Arrays.fill(dis, INF);
        dis[start] = 1;
        //step2
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m; j++) {
                int u = edges[j][0], v = edges[j][1];
                double w = succProb[j];
                //双向松弛
                if(dis[u] >= 0 && dis[v] < dis[u] * w){
                    dis[v] = dis[u] * w;
                }
                if(dis[v] >= 0 && dis[u] < dis[v] * w){
                    dis[u] = dis[v] * w;
                }
            }
        }
        //step3
        return dis[end] == -1 ? 0 : dis[end];
    }
}

4.SPFA + 邻接表 + 类 (最佳)

 /**
     * SPFA + 邻接表
     * 步骤:
     * 1.构图-无向图双向连接，初始化dis,vis和queue
     * 2.调用SPFA算法进行松弛操作
     * 3.根据dis[end]的值决定返回值
     * @param n
     * @param edges
     * @param succProb
     * @param start
     * @param end
     * @return
     */
    final int INF = -1;
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //step1
        int m = edges.length;
        boolean[] vis = new boolean[n];
        double[] dis = new double[n];
        List<List<Pair>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = edges[i][0], v = edges[i][1];
            double w = succProb[i];
            g.get(u).add(new Pair(v, w));
            g.get(v).add(new Pair(u, w));
        }
        Arrays.fill(dis, INF);
        dis[start] = 1;
        vis[start] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        //step2:核心
        while(!queue.isEmpty()){
            int u = queue.poll();
            vis[u] = false;
            for (int i = 0; i < g.get(u).size(); i++) {
                int v = g.get(u).get(i).u;
                double w = g.get(u).get(i).w;
                //松弛
                if(dis[v] < dis[u] * w){
                    dis[v] = dis[u] * w;
                    if(!vis[v]) {
                        vis[v] = true;
                        queue.offer(v);
                    }
                }
            }
        }
        //step3
        return dis[end] == INF ? 0 : dis[end];
    }
    class Pair{
        int u;
        double w;

        public Pair(int _u, double _w) {
            u = _u;
            w = _w;
        }
    }

1976. 到达目的地的方案数

我的题解：

思路:无向图-最短路径-邻接表-dp，该题可以考虑用Dijkstra算法解决，在此基础上需要维护一个计数器数组dp
动态规划
边界条件:dp[0] = 1
递推公式:
$i f (d i s [v] > d i s [u] + w) d p [v] = d p [u]$

$i f (d i s [v] = d i s [u] + w) d p [v] = d p [u] + d p [v]$

步骤:
1.构图，初始化dis,vis和counts
2.调用dijkstra来求最短路并对根据条件求出dp[i]
3.返回counts[n-1]

**TIPS:**这里存储路径长度时需要用long类型，dp中的值在相加时需要进行取模操作
```
class Solution {
 	long INF = Long.MAX_VALUE >> 2;
    int  MOD = (int) (1e9 + 7);
    public int countPaths(int n, int[][] roads) {
        int m = roads.length;
        //step1
        List<List<Pair>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = roads[i][0], v = roads[i][1], w = roads[i][2];
            g.get(u).add(new Pair(v, w));
            g.get(v).add(new Pair(u, w));
        }
        long[] dis = new long[n];
        int[] dp = new int[n];
        boolean[] vis = new boolean[n];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        //边界条件
        dp[0] = 1;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        pq.offer(new long[] {0, 0});
        //step2
        while(!pq.isEmpty()){
            long[] cur = pq.poll();
            int u = (int) cur[0];
            if(vis[u]) continue;
            vis[u] = true;
            for (int i = 0; i < g.get(u).size(); i++) {
                int v = g.get(u).get(i).u, w = g.get(u).get(i).w;
                //计数
                if(dis[u] < INF && dis[v] == dis[u] + w){
                    dp[v] += dp[u];
                    dp[v] %= MOD;
                }
                //覆盖
                else if(dis[u] < INF && dis[v] > dis[u] + w){
                    dp[v] = dp[u];
                    dis[v] = dis[u] + w;
                    pq.offer(new long[]{v, dis[v]});
                }
            }
        }

        //step3
        return dp[n - 1];
    }
    
    class Pair{
        int u;
        int w;

        public Pair(int u, int w) {
            this.u = u;
            this.w = w;
        }
    }
}
```

力扣-最短路

网络延迟时间

我的题解：

787. K 站中转内最便宜的航班

我的题解：

1928. 规定时间内到达终点的最小花费

我的题解：

1334. 阈值距离内邻居最少的城市

我的题解：

1368. 使网格图至少有一条有效路径的最小代价

我的题解：

1514. 概率最大的路径

我的题解：

1976. 到达目的地的方案数

我的题解：