在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）。

解决这个问题，我们将遵循以下步骤−

• 图：由给定边缘列表制成的图的邻接列表

• paths ：大小为（n + 1）并填充为0的数组

• path[n] ：= 1

• dists ：大小为（n + 1）并填充为-1的数组

• q：队列，并且最初插入（0，n）

• 当q不为空时，执行以下操作

  • （dist，node）：= q的前端元素，并将其从q中删除

  • 如果dists [node]与-1不同，则

    • 进行下一次迭代
  • dists [node]：= dist

  • 对于图[node]的每个相邻节点v和重量w，请执行以下操作

    • 如果dists [v]与-1相同，则

    • 在q中插入（dist + w，v）

    • 否则，当dists [v]

    • paths [node]：= paths [node] + paths [v]

  • 如果节点与1相同，则

    • 返回paths [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