Pythonの最初から最後のノードまでの制限されたパスの数を見つけるプログラム

無向加重連結グラフが1つあるとします。グラフには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）があるため、出力は3になります。

これを解決するには、次の手順に従います-

• グラフ：=指定されたエッジリストから作成されたグラフの隣接リスト

• パス：=サイズ（n + 1）の配列で、0で埋められます

• パス[n]：=1

• dists：=サイズ（n + 1）の配列で、-1で埋められます

• q：=キュー、最初に（0、n）を挿入

• qが空でない間、実行します

  • （dist、node）：=qのフロント要素であり、qから削除します

  • dists [node]が-1と同じでない場合、

    • 次のイテレーションに行く

  • dists [node]：=dist

  • 隣接するノードvとgraph[node]の重みwごとに、実行

    • dists [v]が-1と同じ場合、

      • （dist + w、v）をqに挿入します

    • それ以外の場合、dists [v]

      • パス[ノード]：=パス[ノード]+パス[v]

  • ノードが1と同じ場合、

    • リターンパス[ノード]mod10 ^ 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