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] := paths[node] + paths[v]

    • 如果node等於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

更新於：2021年10月6日

202 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告