【面试高频题】结合 DP 的最短路问题

题目描述

这是 LeetCode 上的 1786. 从第一个节点出发到最后一个节点的受限路径数 ，难度为 中等。

Tag : 「最短路」、「线性 DP」

现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges，其中每个 edges[i]=[ui,vi,weighti]edges[i] = [u_{i}, v_{i}, weight_{i}]edges[i]=[ui​,vi​,weighti​] 表示存在一条位于节点 uiu_{i}ui​ 和 viv_{i}vi​ 之间的边，这条边的权重为 weightiweight_{i}weighti​ 。

从节点 start 出发到节点 end 的路径是一个形如 [z0,z1,z2,...,zk][z_{0}, z_{1}, z_{2}, ..., z_{k}][z0​,z1​,z2​,...,zk​] 的节点序列，满足 z0=startz_{0} = startz0​=start 、zk=endz_{k} = endzk​=end 且在所有符合 0<=i<=k−10 <= i <= k-10<=i<=k−1 的节点 ziz_{i}zi​ 和 zi+1z_{i}+1zi​+1 之间存在一条边。

路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。受限路径 为满足 distanceToLastNode(zi)>distanceToLastNode(zi+1)distanceToLastNode(z_{i}) > distanceToLastNode(z_{i}+1)distanceToLastNode(zi​)>distanceToLastNode(zi​+1) 的一条路径，其中 0<=i<=k−10 <= i <= k-10<=i<=k−1 。

返回从节点 1 出发到节点 n 的 受限路径数 。由于数字可能很大，请返回对 109+710^9 + 7109+7 取余 的结果。

示例 1：

输入：n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
输出：3
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是：
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

示例 2：

输入：n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
输出：1
解释：每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是：1 --> 3 --> 7 。

提示：

• 1<=n<=2×1041 <= n <= 2 \times 10^41<=n<=2×104
• n−1<=edges.length<=4×104n - 1 <= edges.length <= 4 \times 10^4n−1<=edges.length<=4×104
• edges[i].length==3edges[i].length == 3edges[i].length==3
• 1<=ui,vi<=n1 <= ui, vi <= n1<=ui,vi<=n
• ui!=viu_i != v_iui​!=vi​
• 1<=weighti<=1051 <= weighti <= 10^51<=weighti<=105
• 任意两个节点之间至多存在一条边
• 任意两个节点之间至少存在一条路径

堆优化 Dijkstra + 动态规划

n 为点的数量，m 为边的数量。

为了方便理解，我们将第 n 个点称为「起点」，第 1 个点称为「结尾」。

按照题意，我们需要先求每个点到结尾的「最短路」，求最短路的算法有很多，通常根据「有无负权边」& 「稠密图还是稀疏图」进行选择。

该题只有正权变，而且“边”和“点”的数量在一个数量级上，属于稀疏图。

因此我们可以采用「最短路」算法：堆优化的 Dijkstra，复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)。

PS. 通常会优先选择 SPFA，SPFA 通常情况下复杂度为 O(m)O(m)O(m)，但最坏情况下复杂度为 O(n×m)O(n \times m)O(n×m)。从数据上来说 SPFA 也会超，而且本题还结合了 DP，因此可能会卡掉图论部分的 SPFA。出于这些考虑，我直接使用堆优化 Dijkstra。

当我们求得了每个点到结尾的「最短路」之后，接下来我们需要求得从「起点」到「结尾」的受限路径数量。

这显然可以用 DP 来做。

我们定义 f(i) 为从第 i 个点到结尾的受限路径数量，f(1) 就是我们的答案，而 f(n) = 1 是一个显而易见的起始条件。

因为题目的受限路径数的定义，我们需要找的路径所包含的点，必须是其距离结尾的最短路越来越近的。

举个🌰，对于示例 1，其中一条符合要求的路径为 1 --> 2 --> 3 --> 5。

这条路径的搜索过程可以看做，从结尾（第 5 个点）出发，逆着走，每次选择一个点（例如 a）之后，再选择下一个点（例如 b）时就必须满足最短路距离比上一个点（点 a）要远，如果最终能选到起点（第一个点），说明统计出一条有效路径。

我们的搜索方式决定了需要先按照最短路距离进行从小到大排序。

不失一般性，当我们要求 f(i) 的时候，其实找的是 i 点可以到达的点 j，并且 j 点到结尾的最短路要严格小于 i 点到结尾的最短路。

符合条件的点 j 有很多个，将所有的 f(j) 累加即是 f(i)。

代码：

class Solution {
    int mod = 1000000007;
    public int countRestrictedPaths(int n, int[][] es) {
        // 预处理所有的边权。 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);
        }

        // 堆优化 Dijkstra：求 每个点 到 第n个点 的最短路
        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]); // 点编号，点距离。根据点距离从小到大
        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 过程
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) arr[i] = new int[]{i + 1, dist[i + 1]}; // 点编号，点距离
        Arrays.sort(arr, (a, b)->a[1]-b[1]); // 根据点距离从小到大排序

        // 定义 f(i) 为从第 i 个点到结尾的受限路径数量
        // 从 f[n] 递推到 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;
                }
            }
            // 第 1 个节点不一定是距离第 n 个节点最远的点，但我们只需要 f[1]，可以直接跳出循环
            if (idx == 1) break;
        }
        return f[1];
    }
}

• 时间复杂度：求最短路的复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)，DP 过程坏情况下要扫完所有的边，复杂度为 O(m)O(m)O(m)。整体复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)
• 空间复杂度：O(n+m)O(n + m)O(n+m)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1786 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。