पायथन में पहले से अंतिम नोड तक प्रतिबंधित पथों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक अप्रत्यक्ष भारित जुड़ा हुआ ग्राफ है। ग्राफ में n नोड्स होते हैं और उन्हें 1 से n तक लेबल किया जाता है। प्रारंभ से अंत तक का पथ [z0, z1, z2, ..., zk] जैसे नोड्स का एक क्रम है, यहां z0 प्रारंभ नोड है और zk अंत नोड है और zi और zi+1 के बीच एक किनारा है जहां 0 <=मैं <=के-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)।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ग्राफ़ :=दी गई किनारे सूची से बने ग्राफ़ की आसन्नता सूची

• पथ :=आकार की एक सरणी (n+1) और 0

  . से भरा हुआ

• पथ[n] :=1

• dists :=आकार की एक सरणी (n+1) और -1 से भरी हुई

• q :=एक कतार, और प्रारंभ में डालें (0, n)

• जबकि q खाली नहीं है, करें

  • (जिला, नोड) :=q का अगला तत्व और इसे q से हटा दें

  • यदि डिस्ट [नोड] -1 के समान नहीं है, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • डिस्ट [नोड] :=जिला

  • ग्राफ के प्रत्येक आसन्न नोड वी और वजन डब्ल्यू के लिए [नोड], करें

    • अगर dists[v] -1 के समान है, तो

      • q में डालें (dist + w, v) q

    • अन्यथा जब डिस्ट[v] <डिस्ट्स[नोड], तब

      • पथ [नोड]:=पथ [नोड] + पथ [v]

  • अगर नोड 1 के समान है, तो

    • वापसी पथ [नोड] मॉड 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