Bellman-Ford और ऋणात्मक चक्र
सभी किनारों पर n-1 रिलैक्सेशन पास चलाइए, अंतिम पास से ऋणात्मक चक्रों का पता लगाइए और समझाइए कि ऋणात्मक भार वाले किनारों पर Dijkstra क्यों विफल होता है।
Bellman-Ford और ऋणात्मक चक्र, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
बेलमैन-फोर्ड क्यों आवश्यक है
बेलमैन-फोर्ड डिज्क्स्ट्रा की तरह एकल-स्रोत सबसे छोटे पथ की समस्या हल करता है, लेकिन यह ऋणात्मक किनारा-भारों को भी संभालता है। यह ऋणात्मक चक्रों का भी पता लगाता है — ऐसे चक्र जिनका कुल भार ऋणात्मक होता है, जिससे उनके माध्यम से किसी परिमित सबसे छोटे पथ को परिभाषित करना असंभव हो जाता है। डिज्क्स्ट्रा से धीमा होने के बावजूद, जब भी ग्राफ़ में ऋणात्मक-भार वाले किनारे हो सकते हैं, बेलमैन-फोर्ड ही सही विकल्प है।
शिथिलीकरण: मूल क्रिया
बेलमैन-फोर्ड एक ही क्रिया पर आधारित है: शिथिलीकरण। किनारे (u, v, w) का शिथिलीकरण करने का अर्थ है: यदि dist[u] + w < dist[v], तो dist[v] = dist[u] + w अद्यतन करें। हम सभी किनारों का बार-बार शिथिलीकरण करते हैं। मुख्य बात यह है: किसी भी सबसे छोटे पथ में अधिकतम V-1 किनारे होते हैं (ऐसे ग्राफ़ में जिसमें ऋणात्मक चक्र न हों)। इसलिए, सभी किनारों पर शिथिलीकरण के V-1 दौर सभी सबसे छोटे पथ खोजने के लिए पर्याप्त हैं।
बेलमैन-फोर्ड का कार्यान्वयन
ग्राफ़ को किनारों की सूची [(u, v, weight)] के रूप में दर्शाएँ। dist[source] = 0 आरंभ करें और बाकी सभी मानों को inf रखें। V-1 दौर चलाएँ और हर दौर में सभी किनारों का शिथिलीकरण करें। यदि Vवें दौर में भी कोई अद्यतन होता है, तो यह ऋणात्मक चक्र का संकेत है।
def bellman_ford(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
# V-1 relaxation passes
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V-th pass: detect negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # negative cycle exists
return dist
edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 2]V-1 दौर पर्याप्त क्यों हैं
ऋणात्मक चक्रों के बिना किसी ग्राफ़ में सबसे छोटे पथ पर प्रत्येक नोड अधिकतम एक बार आता है, इसलिए उसमें अधिकतम V-1 किनारे होते हैं। पहले दौर के बाद, एक-किनारे वाले सबसे छोटे पथ सर्वोत्तम हो जाते हैं। दूसरे दौर के बाद, दो-किनारे वाले सबसे छोटे पथ सर्वोत्तम हो जाते हैं। V-1 दौरों के बाद, सभी सबसे छोटे पथ (जिनमें अधिकतम V-1 किनारे होते हैं) मिल जाते हैं। यदि Vवें दौर में भी कोई दूरी अद्यतन होती है, तो ग्राफ़ में स्रोत से पहुँचने योग्य ऋणात्मक चक्र मौजूद है।
ऋणात्मक चक्रों का पता लगाना
V-1 दौरों के बाद, सभी किनारों पर एक अतिरिक्त दौर चलाएँ। यदि कोई किनारा (u, v, w) dist[u] + w < dist[v] को संतुष्ट करता है, तो एक ऋणात्मक चक्र मौजूद है और कुछ नोडों तक सबसे छोटा पथ -infinity है। वास्तविक अनुप्रयोगों में मुद्रा-विनिमय में लाभार्जन के अवसरों का पता लगाना (log-भार वाले ग्राफ़ों में ऋणात्मक चक्र) और बाधा प्रणालियों में असंगतियों का पता लगाना शामिल है।
def has_negative_cycle(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Nth pass
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return True # negative cycle detected
return False
# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0)) # Trueडिज्क्स्ट्रा और बेलमैन-फोर्ड की तुलना
डिज्क्स्ट्रा: O((V+E) log V), गैर-ऋणात्मक भार आवश्यक, लालची तरीका। बेलमैन-फोर्ड: O(V × E), ऋणात्मक भार संभालता है, ऋणात्मक चक्रों का पता लगाता है। गैर-ऋणात्मक भारों वाली अधिकांश साक्षात्कार समस्याओं के लिए डिज्क्स्ट्रा पसंद किया जाता है। जब ऋणात्मक भार दिखाई दें (जैसे, 'ऋणात्मक लागत वाले किनारों से सबसे छोटा पथ खोजें' या 'मुद्रा-विनिमय लाभार्जन का पता लगाएँ'), तो उत्तर बेलमैन-फोर्ड है। सघन ग्राफ़ों के लिए, बेलमैन-फोर्ड का O(V³) सबसे खराब मामला फ्लॉयड-वॉरशॉल के तुलनीय है।
अनुप्रयोग: बेलमैन-फोर्ड से सबसे सस्ती उड़ानें
K ठहरावों के भीतर सबसे सस्ती उड़ानों (LeetCode 787) को संशोधित बेलमैन-फोर्ड से हल किया जा सकता है: ठीक k+1 शिथिलीकरण दौर चलाएँ (क्योंकि k ठहरावों का अर्थ k+1 किनारे हैं)। पिछले दौर की दूरियों की एक प्रतिलिपि का उपयोग करें, ताकि एक ही दौर में अनुमत सीमा से अधिक छलाँगें न लगें — अन्यथा एक ही दौर में कई छलाँगें जुड़ सकती हैं।
def findCheapestPrice_bf(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:] # copy to avoid using updated dist in same pass
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1
print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200SPFA: कतार-आधारित अनुकूलन
सबसे छोटे पथ का तेज़ एल्गोरिदम (SPFA) बेलमैन-फोर्ड का एक अनुकूलित रूप है, जो कतार का उपयोग करके केवल उन नोडों से जुड़े किनारों का दोबारा शिथिलीकरण करता है जिनकी दूरी अभी-अभी अद्यतन हुई है। औसत स्थिति O(E) है, लेकिन सबसे खराब स्थिति अब भी O(V × E) रहती है। साक्षात्कारों में SPFA की आवश्यकता बहुत कम पड़ती है, लेकिन जब विरल ग्राफ़ों पर बेलमैन-फोर्ड बहुत धीमा हो, तब आप इसे अनुकूलन के रूप में बता सकते हैं। पाइथन में SPFA पहले से उपलब्ध नहीं है, लेकिन इसे collections.deque के साथ लागू करना सरल है।
मुद्रा-विनिमय लाभार्जन का पता लगाना
बेलमैन-फोर्ड का एक प्रसिद्ध अनुप्रयोग: मुद्रा-विनिमय दरें दी गई हों, तो पता लगाएँ कि लाभार्जन संभव है या नहीं (ऐसा चक्र जिसमें मुद्राओं को बदलने पर शुरुआत से अधिक राशि वापस मिले)। विनिमय दरों का ऋणात्मक लघुगणक लेकर रूपांतरण करें। मुद्रा-विनिमय लाभार्जन = ऋणात्मक कुल log-भार वाला चक्र = ऋणात्मक चक्र, जिसका बेलमैन-फोर्ड से पता लगाया जा सकता है। इससे वास्तविक दुनिया की वित्तीय समस्याएँ मानक एल्गोरिदम में बदली जा सकती हैं।
import math
def has_arbitrage(rates):
n = len(rates)
# Transform: -log(rate) converts product to sum
log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
dist = [float('inf')] * n
dist[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # arbitrage!
return Falseशीघ्र समाप्ति का अनुकूलन
यदि सभी किनारों पर पूरे दौर में कोई दूरी अद्यतन नहीं होती, तो बाद के दौरों में भी कुछ अद्यतन नहीं होगा — इसलिए जल्दी रुक जाएँ। यह अनुकूलन सबसे अच्छी स्थिति की जटिलता को O(E) तक घटा देता है, जब कुछ ही दौरों के बाद ग्राफ़ पहले से ही सर्वोत्तम स्थिति में हो। प्रत्येक दौर की शुरुआत में updated = False ध्वज जोड़ें; यदि दौर के बाद भी यह False रहे, तो तुरंत रुक जाएँ।
def bellman_ford_optimised(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # no more improvements possible
return distसन्निकटता सूचियों वाले ग्राफ़ों पर बेलमैन-फोर्ड
जब ग्राफ़ किनारों की सूची के बजाय सन्निकटता सूची के रूप में दिया गया हो, तो पहले उसे किनारों की सूची में बदलें या सन्निकटता सूची की सभी प्रविष्टियों पर किनारों की तरह पुनरावृत्ति करें। V=1000 और E=5000 के लिए, V-1=999 दौरों में प्रत्येक बार 5000 किनारों को जाँचने पर 4,995,000 क्रियाएँ होती हैं — जो समय-सीमाओं के भीतर है। बहुत सघन ग्राफ़ों (E ≈ V²) के लिए O(V³) का सबसे खराब मामला फ्लॉयड-वॉरशॉल से मेल खाता है, इसलिए चुनाव संदर्भ पर निर्भर करता है।
from collections import defaultdict
def bellman_ford_adj(V, adj, source):
# Convert adjacency list to edge list
edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distत्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाएँ एवं एल्गोरिदम — कोडिंग इंटरव्यू तैयारी की अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: ऋणात्मक-भार वाले किनारों को संभालने के लिए बेलमैन-फोर्ड सभी किनारों का V-1 बार शिथिलीकरण करता है, यदि Vवाँ शिथिलीकरण दौर भी सुधार पाता है, तो यह ऋणात्मक चक्र का संकेत है, और एल्गोरिदम की जटिलता O(V × E) है, जबकि डिज्क्स्ट्रा की O((V+E) log V) है। आगे हम एक ही O(V³) गणना में सभी युग्मों के सबसे छोटे पथों के लिए फ्लॉयड-वॉरशॉल पढ़ेंगे।
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “Bellman-Ford और ऋणात्मक चक्र” पाठ निःशुल्क है?
हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “Bellman-Ford और ऋणात्मक चक्र” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Bellman-Ford और ऋणात्मक चक्र” में मैं क्या सीखूँगा?
सभी किनारों पर n-1 रिलैक्सेशन पास चलाइए, अंतिम पास से ऋणात्मक चक्रों का पता लगाइए और समझाइए कि ऋणात्मक भार वाले किनारों पर Dijkstra क्यों विफल होता है। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ DSA Interview Prep का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।
“Bellman-Ford और ऋणात्मक चक्र” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम
- Bellman-Ford और ऋणात्मक चक्र
- Floyd-Warshall: सभी युग्मों के सबसे छोटे पथ
- नेटवर्क विलंब समय और पथ पुनर्निर्माण