Competitive Programming Academy · पाठ

Bellman-Ford और Negative Edges

negative values सँभालें और cycles खोजें

पाठ 3, कुल 4 में से13 चरण

Bellman-Ford और Negative Edges, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

डिज्क्स्ट्रा कब विफल होता है

डिज्क्स्ट्रा भरोसा करता है कि निकाली गई दूरी अंतिम है, लेकिन कोई ऋणात्मक किनारा बाद में किसी पथ को सस्ता बना सकता है। इसलिए यह विफल हो जाता है।

बेलमैन-फोर्ड का उपयोग

बेलमैन-फोर्ड ऋणात्मक किनारों के भार को संभालता है। यह डिज्क्स्ट्रा से धीमा है, लेकिन वहाँ भरोसेमंद है जहाँ लालची तर्क पर विश्वास नहीं किया जा सकता।

मूल प्रक्रिया

यह हर किनारे पर बार-बार दूरी-सुधार करता है: यदि dist[u] और किनारे के भार का योग dist[v] से छोटा हो, तो dist[v] को उस छोटी मान पर बदल देता है।

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

कितने चरण चाहिए

सबसे छोटा पथ अधिकतम V - 1 किनारों का उपयोग करता है, इसलिए हर किनारे पर दूरी-सुधार के V - 1 चरण सभी दूरियों को निश्चित करने के लिए पर्याप्त हैं।

for _ in range(n - 1):
    relax_all_edges()

दूरियाँ आरंभ करें

स्रोत को शून्य पर रखकर बाकी हर दूरी को अनंत से शुरू करें, ठीक वैसे ही जैसे डिज्क्स्ट्रा में करते हैं।

dist = [float('inf')] * n
dist[src] = 0

एक पूरा चक्र

हर चरण में किनारों की पूरी सूची पर एक बार जाएँ और हर किनारे की दूरी सुधारें। हर चरण में सुधार एक किनारे आगे तक फैलता है।

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

V - 1 पर्याप्त क्यों है

k चरणों के बाद k किनारों वाले सभी सबसे छोटे पथ सही हो जाते हैं। V - 1 चरणों तक हर सरल सबसे छोटा पथ पूरा हो जाता है।

अतिरिक्त चरण

एक और चरण चलाएँ। यदि कोई दूरी अब भी घटती है, तो लागत लगातार कम हो रही है, जो ऋणात्मक चक्र का संकेत है।

ऋणात्मक चक्रों का पता लगाना

ऋणात्मक चक्र का अर्थ है कि कोई सीमित सबसे छोटा पथ मौजूद नहीं है, क्योंकि लागत को बिना सीमा घटाने के लिए आप हमेशा चक्र में घूमते रह सकते हैं।

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

चलने का समय

आप V चरणों में E किनारों की दूरियाँ सुधारते हैं, इसलिए बेलमैन-फोर्ड की जटिलता O(V * E) होती है, जो छोटे या मध्यम ग्राफ़ के लिए ठीक है।

डिज्क्स्ट्रा या बेलमैन-फोर्ड

गैर-ऋणात्मक भार और गति के लिए डिज्क्स्ट्रा चुनें। ऋणात्मक भार होने पर या किसी खराब चक्र का पता लगाना हो, तो बेलमैन-फोर्ड चुनें।

त्वरित जाँच

V - 1 चरणों के बाद एक और चरण में कोई दूरी घट जाती है। इसका क्या अर्थ है?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: बेलमैन-फोर्ड

V - 1 चरणों तक सभी किनारों की दूरियाँ सुधारें, फिर ऋणात्मक चक्रों का पता लगाने के लिए एक और चरण चलाएँ। इसकी जटिलता O(V*E) है, लेकिन यह वहाँ भी काम करता है जहाँ डिज्क्स्ट्रा नहीं कर सकता। ✅

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Bellman-Ford और Negative Edges” पाठ निःशुल्क है?

हाँ—“Bellman-Ford और Negative Edges” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Bellman-Ford और Negative Edges” में मैं क्या सीखूँगा?

negative values सँभालें और cycles खोजें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।

“Bellman-Ford और Negative Edges” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← Competitive Programming Academy पर वापस जाएँ