leetcode之最短路刷题总结1_leetcode 最短路

leetcode之最短路刷题总结1

**最短路：**给定两个顶点，在以这两个 顶点为起点和终点的路径中，边的权值和最小的路径。

最短路径中有几种经典的算法，我们主要练习的是Dijkstra算法和Floyd算法，分别用于解决单元最短路径问题和多源最短路径问题。

Dijkstra算法适用于单源最短路径，具体地，找到最短路已经确定的节点，从它出发更新相邻节点的最短距离。

Floyd算法适用于多源最短路径，具体地，通过一系列n阶矩阵来计算一个n节点加权图的最短距离。每轮让第k个节点做中转节点，更新第i个节点到第j个节点的最短路径。

1-阈值距离内邻居最少的城市
题目链接：题目链接戳这里！！！

思路：Floyd算法
本题需要记录每个节点到其它节点的最短路径，所以通过Floyd算法，使用dp数组更新所有节点到其余节点的最短路径，最后dp数组保留的就是所有节点到其余节点的最短路径，使用num数组记录，每个节点到其它节点的最短路长度小于distanceThreshold的个数，找出最少的个数的起点i就是答案。

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        //多源最短路径，使用Floyd算法
        int m = edges.length ;
        int [][] dp = new int [n][n] ;//n阶矩阵计算一个n节点的加权图的最短路径
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                dp[i][j] = 1000000000 ;
            }
        }
        for(int i=0; i<n; i++){
            dp[i][i] = 0 ;
        }

        for(int [] edge : edges){
            int u=edge[0], v = edge[1], w = edge[2] ;
            dp[u][v] = dp[v][u] = w ;
        }

        for(int k=0; k<n; k++){ //k作为中转节点,更新i节点到j节点的最短路径
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]) ;
                }
            }
        }

        int [] num = new int [n] ; //记录所有节点可到达的路径数量
        int min = 1000000000, pos = -1 ;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j){
                    continue ;
                }
                if(dp[i][j] <= distanceThreshold){
                    num[i] ++ ;
                }
            }
            if(min >= num[i]){
                min = num[i] ;
                pos = i ;
            }
        }
        return pos ;
    }
}
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

2-到达目的地的方案数
题目链接：题目链接戳这里！！！

思路：Dijkstra算法
这是个单源最短路问题，可以使用Dijkstra算法，dist[i][0]记录到达第i个节点的最短路径长度，dist[i][1]记录到达第i个节点的最短路径条数。

使用优先队列，对所用时间按升序排序，如果时间相等按节点大小升序排序。每次选一个用时最短的，如果通过原始节点到达该节点的距离小于初始值，则更新最短距离，如果节点的最短路已经确定，则直接跳过。

class Solution {
    public int countPaths(int n, int[][] roads) {
        //花费最少时间从路口0到路口n-1的方案数，单源最短路径问题，可以使用Dijkstra
        final int INF = Integer.MAX_VALUE ;
        int mod = 1000000007 ;
        List<int []> []g = new List[n] ;
        for(int i=0; i<n; i++){
            g[i] = new ArrayList<int []>() ;
        }
        for(int [] road : roads){
            int u = road[0], v = road[1], w = road[2] ;
            g[u].add(new int [] {v,w}) ;
            g[v].add(new int [] {u,w}) ;
        }
        int [][] dist = new int [n][2] ;
        for(int i=0; i<n; i++){
            dist[i][0] = INF ;
        }

        dist[0][0] = 0 ; //到达0节点的最短路径长度
        dist[0][1] = 1 ; //到达0节点的最短路条数
        

        PriorityQueue<int []> queue = new PriorityQueue<int []>((a,b)->a[1]!=b[1]?a[1]-b[1]:a[0]-b[0]) ;
        queue.add(new int []{0,0}) ; //数组中的两个值，一个是到达的节点和时间
        while(!queue.isEmpty()){
            int [] p = queue.poll() ;
            int x = p[0], time = p[1] ;
            if(dist[x][0] < time){ //最短路已经确定
                continue ;
            }
            for(int [] edge : g[x]){
                int y = edge[0], d = dist[x][0] + edge[1] ;
                if(d==dist[y][0]){
                    dist[y][1] += dist[x][1] ;
                    dist[y][1] = dist[y][1] % mod ;
                }
                if(d<dist[y][0]){ //更新最短距离
                   dist[y][0] = d ;
                   queue.add(new int []{y, d}) ;
                   dist[y][1] = dist[x][1] ;
                }
            }
        }
        return dist[n-1][1] ;
    }
}
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

思路2：当然这个题也可以用Floyd去解决，具体如下：

dist[i][j]记录从i到j的最短路长度
ways[i][j]记录从i到j最短路的条数
每轮让第k个节点做中转节点，更新第i个节点到第j个节点的最短路径。

由于Floyd是O(n^3)复杂度，显然不如Dijkstra效率高。

class Solution {
    public int countPaths(int n, int[][] roads) {
       if(n<=2){
           return 1 ;
       }
       int mod = 1000000007 ;
       long [][] dist = new long [n][n] ;
       long [][] ways = new long [n][n] ;

       for(int i=0; i<n; i++){
           Arrays.fill(dist[i],Long.MAX_VALUE) ;
       }

       for(int i=0; i<n; i++){
           dist[i][i] = 0 ;
       }

       for(int [] edge : roads){
           int u = edge[0], v = edge[1], w = edge[2] ;
           dist[u][v] = dist[v][u] = w ;
           ways[u][v] = ways[v][u] = 1 ;
       }

       for(int k=0; k<n; k++){
           for(int i=0; i<n; i++){
               if(dist[i][k]==Long.MAX_VALUE){
                   continue ;
               }
               for(int j=0; j<n; j++){
                   if(dist[k][j] == Long.MAX_VALUE){
                       continue ;
                   }
                   if(dist[i][j] < dist[i][k] + dist[k][j]){
                       continue ;
                   }
                   if(dist[i][j] > dist[i][k] + dist[k][j]){
                       //遇到最短路
                       ways[i][j] = ways[i][k] * ways[k][j] ;
                   }else{
                       //遇到相等的最短路
                       ways[i][j] += ways[i][k] * ways[k][j] ;
                   }
                    ways[i][j] = ways[i][j] % mod ;
                    dist[i][j] = dist[i][k] + dist[k][j] ;
               }
           }
       }
       return (int) ways[0][n-1] ;
    }
}
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

3-网络延迟时间
题目链接：题目链接戳这里！！！

思路：Dijkstra算法
单源最短路径问题，可以使用Dijkstra算法计算出k点到其它点的最短路径，然后取所有最短路的最大值。

class Solution {
   public int networkDelayTime(int[][] times, int n, int k) {
     //单源最短路径问题，可以使用Dijkstra算法计算出k点到其它点的最短路径，然后取所有最短路的最大值
     int [][] g = new int [n][n] ;
     int [] dist = new int [n] ;
     int INF = Integer.MAX_VALUE / 2;
     for(int i=0; i<n; i++){
         Arrays.fill(g[i], INF) ;
     }
     for(int [] edge : times){
         int u = edge[0]-1, v = edge[1]-1, w = edge[2] ;
         g[u][v] = w ;
     }
     Arrays.fill(dist,INF) ;
     dist[k-1] = 0 ;
   
     boolean [] vis = new boolean[n] ; //记录当前节点是否找出最短路径
      
     for(int i=0; i<n; i++){
         int x = -1 ;
         for(int y=0; y<n; y++){
             if(!vis[y] && (x==-1 || dist[x]>dist[y])){
                 x = y ;
             }
         }
         vis[x] = true ;
         for(int y=0; y<n; y++){
             dist[y] = Math.min(dist[y], dist[x]+g[x][y]) ;
         }
     }
     int ans = Integer.MIN_VALUE ;
     for(int d : dist){
         ans = Math.max(ans, d) ;
     }
     return ans == INF ? -1 : ans ;

    }
}
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

4-概率最大的路径
题目链接：题目链接戳这里！！！

思路：用Dijkstra求单源最大概率路径，和求最短路径一样的思路。只不过优先队列按照最大的权值排序，每次取出的是最大权值的，找更大权值的去更新当前的权值。

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //Dijkstra算法，找出最大的概率路径的概率
  
        List<double[]> [] g = new List[n] ;

        for(int i=0; i<n; i++){
            g[i] = new ArrayList<double[]>() ;
        }

        for(int i=0; i<edges.length; i++){
            int u =edges[i][0], v = edges[i][1] ;
            double w = succProb[i] ;
            g[u].add(new double [] {v, w}) ;
            g[v].add(new double [] {u, w}) ;
        }

       
        //自定义排序，优先更显概率大的节点
        PriorityQueue<State> queue = new PriorityQueue<State>((a,b)->{
            if(a.pro>b.pro){
                return -1;
            }else if(a.pro<b.pro){
                return 1 ;
            }else {
                return 0 ;
            }
        }) ; 

        double [] ans = new double [n] ;
        ans[start] = 1.0 ;
        queue.add(new State(start,1)) ;
        while(!queue.isEmpty()){
            State curNode = queue.poll() ;
            if(curNode.id==end){
                return curNode.pro ;
            }
            for(double [] neigbors : g[curNode.id]){
                int nextId = (int)neigbors[0] ;
                double nextPro = curNode.pro * neigbors[1] ;
                if(nextPro > ans[nextId]){
                    ans[nextId] = nextPro ;
                    queue.add(new State(nextId, nextPro)) ;
                }
            }
        }
        return ans[end] ;
      
    }
}
class State{
    int id ;
    double pro ;
    public State(int id, double pro){
        this.id = id ;
        this.pro = pro ;
    }
}
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

**

每走的一步路都算数，日拱一卒无有尽，功不唐捐终入海！！！

**