用 Python 编写程序，查找从第一个节点到最后一个节点的受限路径数
假设我们有一个无向加权连通图。该图有 n 个节点，它们被标记为从 1 到 n。从起点到终点的路径是一系列节点，如 [z0, z1, z2, ..., zk]，其中 z0 是起始节点，zk 是终止节点，zi 和 zi+1 之间有一条边，其中 0 <= i <= k-1。路径的距离是路径边缘权重值的总和。让 dist(x) 表示从节点 n 到节点 x 的最短距离。受限路径是一种特殊路径，它还满足 dist(zi) > dist(zi+1)，其中 0 <= i <= k-1。因此，我们必须找到从节点 1 到节点 n 的受限路径数。如果答案太大，则返回答案模 10^9 + 7。
因此，如果输入如下
那么输出将是 3，因为有三个受限路径 (1,2,5)、(1,2,3,5)、(1,3,5)。
为了解决这个问题，我们将遵循以下步骤 −
graph := 由给定边列表组成的图的邻接列表
paths := 大小为 (n+1) 的数组，并填充0
paths[n] := 1
dists := 一个大小为 (n+1) 的数组，并填充 -1
q := 一个队列，最初插入 (0, n)
当 q 不为空时，执行
(dist, node) := q 的前元素并将其从 q 中删除
如果 dists[node] 不等于 -1，则
进行下一次迭代
dists[node] := dist
对于 graph[node] 的每个相邻节点 v 和权重 w，执行
如果 dists[v] 与 -1 相同，则
将 (dist + w, v) 插入 q
否则，当 dists[v] < dists[node] 时，则
paths[node] := routes[node] + routes[v]
如果 node 与 1 相同，则
返回 routes[node] mod 10^9+7
返回 0
示例
让我们看看下面的实现以便更好地理解 −
from collections import defaultdict from heapq import heappop, heappush def solve(n, edges): graph = defaultdict(dict) for u, v, w in edges: graph[u][v] = w graph[v][u] = w paths = [0] * (n+1) paths[n] = 1 dists = [-1] * (n+1) q = [(0, n)] while q: dist, node = heappop(q) if dists[node] != -1: continue dists[node] = dist for v, w in graph[node].items(): if dists[v] == -1: heappush(q, (dist + w, v)) elif dists[v] < dists[node]: paths[node] += paths[v] if node == 1: return paths[node] % (10**9 + 7) return 0 n = 5 edges = [(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)] print(solve(n, edges))
输入
5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
输出
3
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
