在 Python 中查找从第一个节点到最后一个节点的受限路径数的程序

假设我们有一个无向加权连通图。该图有 n 个节点，它们的标签从 1 到 n。从开始到结束的路径是一系列节点，例如 [z0, z1, z2, ..., zk] 这里 z0 是开始节点，zk 是结束节点，在 zi 和 zi+1 之间有一条边，其中 0 <=我 <= k-1。路径的距离是路径边缘的权重值之和。Letdist(x)表示距节点n和节点x的最短距离。受限路径是一条特殊路径，它也满足dist(zi)> dist(zi+1) where 0 <= i <= k-1。因此，我们必须找到从节点 1 到节点 n 的受限路径的数量。如果答案太大，则返回模 10^9 + 7 的答案。

所以，如果输入像

那么输出将为 3，因为存在三个受限路径 (1,2,5)，(1,2,3,5)，(1,3,5)。

示例

让我们看看以下实现以更好地理解 -

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