Java 中从第一个节点到最后一个节点的受限路径数量

给定一个无向加权连通图。正整数 n 表示图中有 n 个节点，编号从 1 到 n。我们还提供了一个边数组，其中 edges[i] = [ui, vi, weighti] 表示节点 ui 和 vi 之间存在一条边，权重为 weight i。如果 0 <= i <= k-1，则节点 zi 和 zi+1 之间存在一条边，而节点 start 到节点 end 的路径是节点序列 [z0, z1, z2,..., zk]，其中 z0 = start 且 zk = end。

路径上边的总权重决定了其长度。节点 n 到节点 x 的最短路径长度由变量 distanceToLastNode(x) 表示。如果一条路径还满足条件 distanceToLastNode(zi) > distanceToLastNode(zi+1)，其中 0 <= i <= k-1，则该路径被认为是受限路径。返回节点 1 到节点 n 之间有多少受限路径。由于数量可能很多，请以 10^9 + 7 取模返回该数量。

示例 1

输入

int n = 5

int edge = [[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

输入

int n = 7

int edge = [[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. 1 --> 3 --> 7.

方法：最短路径计算（Dijkstra 算法）

我们首先应用 Dijkstra 算法来确定每个节点到节点 n 的最短路径。通过使用优先队列（最小堆），可以有效地获得具有最短距离的下一个节点。我们使用计算出的距离来计算从节点 1 到节点 n 的受限路径数量。为了确保在处理一个节点之前，所有距离更短的节点都已得到处理，我们使用优先队列按它们与节点 n 的距离排序来处理节点。

如果对于每个节点 x 和每个邻居 y，从 y 到 n 的距离大于从 x 到 n 的距离（distance[y] > distance[x]），那么我们可以沿着受限路径从 x 移动到 y。然后将到达 x 的受限路径数量添加到到达 y 的受限路径数量中进行更新。

算法

步骤 1：为了表示图，创建一个邻接表。每个节点都将包含一个配对列表，其中每个配对由连接到相邻节点的边的权重组成。

步骤 2：对于输入中的每一条边，将匹配的配对添加到两个节点的邻接表中。

步骤 3：构建一个名为“distance”的数组，用于存储每个节点到节点 n 的最短路径。将所有距离初始化为无穷大，节点 n 除外，其值为 0。

步骤 4：将节点 n 的计数设置为 1 后，创建一个名为 ans 的数组来计算每个节点到节点 n 的受限路径数量。

步骤 5：使用优先队列（最小堆）实现 Dijkstra 方法。首先添加节点 n，确保其距离为 0。

步骤 6：当优先队列仍已填充时，应用 Dijkstra 算法。

在步骤 6.1 中提取距离最近的节点。

步骤 6.2：如果此距离大于节点记录的距离，则继续到下一个迭代。

步骤 6.3：如果发现到邻居的更短路径，则更新邻居的距离并将其添加到优先队列中。

步骤 6.4：如果节点之间的距离大于到当前节点的距离，则将当前节点的受限路径数量添加到邻居的受限路径数量中。

步骤 7：返回从节点 1 到节点 n 的受限路径数量。

实施

文件名：RestrictedPaths.java

输出

 
The number of restricted paths is: 3   

复杂度分析

上述代码的时间复杂度为 O((n+m)logn)，空间复杂度为 O(n+m)。