This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1786 on LeetCode. The number of limited paths from the first node to the last node, with medium difficulty.

Tag: “Graph theory shortest circuit”, “linear DP”

There is a weighted undirected connected graph. You are given a positive integer n, indicating that there are n nodes in the graph, numbered from 1 to n; Give you another array edge, where each edge [I] = [UI, vi, weighti] indicates that there is an edge between the node UI and vi, and this edge has weighti.

The path from node start to node end is a sequence of nodes like [z0, z1, z2… zk], Z0 = start, zk = end, and there is an edge between zi and zi+1 in all nodes conforming to 0 <= I <= k-1.

The distance of a path is defined as the sum of the weights of all edges along the path. DistanceToLastNode (x) indicates the shortest distance between nodes N and x. The restricted path is a path satisfying distanceToLastNode(zi) > distanceToLastNode(zi+1), where 0 <= I <= k-1.

Returns the number of restricted paths from node 1 to node n. Because the numbers can be large, return mod 109 + 7.

Example 1:

Input: n = 5, edges = [[1, 2, 3], filling [1], [2,3,1],,4,2 [1], [5,2,2], [3,5,1], [5,4,10]] output: three possibilities: Each circle contains the node number in black and the distanceToLastNode value in blue. Three restricted path respectively is: 1) 1 - > 2 - > 5 2) 1 - > 2 - > 3 - > 5 3) 1 - > 3 - > 5Copy the code

Example 2:

Input: n = 7, edges = [,3,1 [1], [4,1,2], [4] 7,,5,3 [2], [5,6,1], [6,7,2],,5,3 [7], [2,6,4]] output: 1: Each circle contains the node number in black and the distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.Copy the code

Tip:

  • 1 <= n <= 2 *
    1 0 4 10^4
  • n – 1 <= edges.length <= 4 *
    1 0 4 10^4
  • edges[i].length == 3
  • 1 <= ui, vi <= n
  • ui ! = vi
  • 1 <= weighti <=
    1 0 5 10^5
  • There is at most one edge between any two nodes
  • At least one path exists between any two nodes

Dijkstra + dynamic programming solution for heap optimization

N is the number of points, m is the number of edges.

For ease of understanding, we call the NTH point “the beginning” and the first point “the end”.

According to the meaning of the question, we need to find the “shortest circuit” of each point to the end, there are many algorithms to find the shortest circuit, usually according to “with or without negative weight edge” & “dense graph or sparse graph” to choose.

This problem has only positive contingency, and the number of “edges” and “points” is in an order of magnitude, which belongs to the sparse graph.

So we can use the “shortest” algorithm: Dijkstra for heap optimization, O(mlog⁡n)O(m\log{n})O(mlogn).

PS. SPFA is usually preferred, and the complexity of SPFA is
O ( m ) O(m) , but the worst case complexity is
O ( n ∗ m ) O(n*m) . In terms of data, SPFA will also exceed DP, so SPFA may be blocked in the graph theory part. For these reasons, I use heap optimization Dijkstra directly.

Once we have found the “shortest path” from each point to the end, we then need to find the number of constrained paths from “start” to “end”.

This is obviously something you can do with DP.

We define f(I) as the limited number of paths from the ith point to the end, f(1) is our answer, and f(n) = 1 is an obvious starting condition.

Because of the limited definition of the number of paths, we need to find a path that contains points that are closer and closer to the shortest path at the end.

For example 🌰, for example 1, one of the paths that meets the requirements is 1 –> 2 –> 3 –> 5.

This path search process can be regarded as, starting from the end (5 points), go against, each time you select a point (a), for example, to select the next point (e.g., b) when they have to meet the most short distance than the last one point (point a) much, if finally can choose to start () the first point, explain the statistical out a valid path.

Our search method determines that we need to sort from smallest to largest according to the shortest distance.

Without loss of generality, when we’re looking for f of I, we’re looking for the point j that I can reach, and the shortest path from j to the end is going to be strictly less than the shortest path from I to the end.

There are a lot of points j, so if you add up all the points f(j), that’s f(I).

Code:

class Solution {
    int mod = 1000000007;
    public int countRestrictedPaths(int n, int[][] es) {
        // Preprocess all edge weights. a b w -> a : { b : w } + b : { a : w }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>(); 
        for (int[] e : es) {
            int a = e[0], b = e[1], w = e[2];
            Map<Integer, Integer> am = map.getOrDefault(a, new HashMap<Integer, Integer>());
            am.put(b, w);
            map.put(a, am);
            Map<Integer, Integer> bm = map.getOrDefault(b, new HashMap<Integer, Integer>());
            bm.put(a, w);
            map.put(b, bm);
        }

        // Heap optimization Dijkstra: find the shortest from each point to the NTH point
        int[] dist = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        Queue<int[]> q = new PriorityQueue<int[]>((a, b)->a[1]-b[1]); // Point number, point distance. From small to large according to the distance between points
        q.add(new int[]{n, 0});
        while(! q.isEmpty()) {int[] e = q.poll();
            int idx = e[0], cur = e[1];
            if (st[idx]) continue;
            st[idx] = true;
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int i : mm.keySet()) {
                dist[i] = Math.min(dist[i], dist[idx] + mm.get(i));
                q.add(new int[]{i, dist[i]}); }}/ / dp process
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) arr[i] = new int[]{i + 1, dist[i + 1]}; // Point number, point distance
        Arrays.sort(arr, (a, b)->a[1]-b[1]); // Sort by point distance from smallest to largest

        // Define f(I) as the number of limited paths from the ith point to the end
        // From f[n] to f[1]
        int[] f = new int[n + 1]; 
        f[n] = 1;
        for (int i = 0; i < n; i++) {
            int idx = arr[i][0], cur = arr[i][1];
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int next : mm.keySet()) {
                if(cur > dist[next]) { f[idx] += f[next]; f[idx] %= mod; }}// The first node is not necessarily the farthest point from the NTH node, but we just need f[1] to jump out of the loop
            if (idx == 1) break;
        }
        return f[1]; }}Copy the code
  • Time complexity: to find the shortest circuit complexity is O(mlog⁡n)O(m\log{n})O(mlogn), DP process in bad case to sweep all edges, complexity is O(m)O(m)O(m) O(m)O(m). The overall complexity is O(mlog⁡n)O(m\log{n})O(mlogn)
  • Space complexity: O(n+m)O(n +m)O(n +m)

The last

This is the No.1786 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.