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

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