Bellman–Ford, negative cycles और Floyd–Warshall
संबंध और contract
Dijkstra relaxation तथा DP state design आधार हैं। Directed weighted graph में negative weights मान्य हैं। Walk vertices/edges दोहरा सकता है। Source से negative-total cycle reachable हो तो उस cycle के आगे reachable vertices की finite minimum walk weight नहीं: cycle दोहराकर weight मनचाहा घटाएँ। जो vertices cycle से reachable नहीं, वे अपने-आप प्रभावित नहीं। Unreachable negative cycle इस source की finite distances नहीं बिगाड़ता।
1. Edge-bounded DP के रूप में Bellman–Ford
B_k[v]=source से v तक अधिकतम k edges वाले walk की minimum weight। B_0[s]=0, बाकी ∞। अलग previous/current arrays में:
B_k[v]=min(B_(k−1)[v], min over (u,v) of B_(k−1)[u]+w(u,v)); finite predecessor की शर्त रखें।
Walk या पहले ही k−1 edges तक है, या अंतिम (u,v) edge जोड़ता है। यही recurrence proof। Source-reachable negative cycle न हो तो shortest walk के cycles weight बढ़ाए बिना हटा सकते हैं; simple path में अधिकतम V−1 edges। इसलिए V−1 passes पर्याप्त।
सामान्य code हर pass में edges in-place relax करता है। Edge order से एक pass में कई edges propagate हो सकते हैं; intermediate array को exact B_k न कहें। फिर भी k passes के बाद वह at-most-k optimum से खराब नहीं; finite shortest solution हो तो V−1 passes पर्याप्त। पूरा pass कोई improvement न करे तो early stop।
2. Pass trace और cycle test
s→a=4,s→b=5,a→b=−2। Separate arrays: B_0=(0,∞,∞), B_1=(0,4,5), B_2=(0,4,2)। b का final path s,a,b, cost 2। In-place order s→a,a→b,s→b से पहले pass में b=2 हो सकता है।
V−1 passes के बाद एक extra scan करें। Finite d[u] वाला edge d[u]+w(u,v)<d[v] दे तो source-reachable negative cycle है। Finite guard disconnected cycle बाहर रखता है। इससे सभी vertices −∞ नहीं हो जाते। Affected vertices पहचानने के लिए अभी relaxable edges के endpoints लेकर उनसे outgoing traversal करें; downstream vertices reachable negative cycle से प्रभावित हैं। Parent tracking और V backward steps cycle locate करने में सहायक हैं, पर detection मात्र से बिना reconstruction logic सही printed cycle नहीं मिलता।
उदाहरण s→a=1,a→b=1,b→a=−3,b→t=2 और s से अलग x→x=−1। a→b→a weight −2 reachable है; a,b,t की finite minimum नहीं। वापस s का route न हो तो s=0 रहता है। x cycle unreachable है, इसलिए s की दूसरी distances नहीं बदलती। इस directed model में self-loops मान्य हैं।
3. Floyd–Warshall में intermediate vertices
All-pairs के लिए vertices 1,...,V। D^(k)[i,j]=केवल {1,...,k} से internal vertices लेने वाले path/walk की minimum weight, जब relevant negative cycle न हो। D^(0)[i,i]=0; बाकी least direct edge या ∞। Diagonal पर भी direct negative self-loop और 0 का minimum लें, ताकि loop खो न जाए।
D^(k)[i,j]=min(D^(k−1)[i,j], D^(k−1)[i,k]+D^(k−1)[k,j])।
Shortest path या k नहीं लेता, या k पर दो earlier-internal-vertex paths में टूटता है। Standard in-place order में k सबसे बाहर, फिर i,j; addition से पहले finite checks। यह edge-count DP नहीं। a→b=3,b→c=−1,a→c=7 में b allow करने वाला stage a→c को 2 करता है।
4. Negative cycles, लागत और गलतियाँ
अंत में D[k,k]<0 negative cycle दर्शाता है। Pair (i,j) तभी unbounded-below है जब i से कोई negative-cycle vertex k reachable हो और k से j reachable हो। बाकी pairs finite या ∞ रह सकते हैं। Affected raw entries valid finite shortest distances नहीं हैं।
Bellman–Ford passes O(VE), initialization O(V), auxiliary distances/parents O(V); separate-array भी O(V)। Floyd–Warshall Θ(V³) time, Θ(V²) matrix storage। Negative cycle न होने से Dijkstra valid नहीं बनता; negative edge ही उसे गलत कर सकता है। Infinity arithmetic guard करें, reachable/global cycles अलग रखें और Floyd में k outermost रखें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Source-reachable negative cycle न हो तो Bellman–Ford कितने full passes तक?
A. 1 always B. V−1 C. E−1 always D. V²
उत्तर: B
A: एक pass सारे paths नहीं पहुँचाता।
B: Simple shortest path में V−1 edges तक।
C: यह standard pass bound नहीं।
D: Quadratic passes अनावश्यक।
P02. Extra relaxable edge पर source-reachable cycle test में कौन-सी guard?
A. d[u] finite है B. w(u,v) positive है C. u source है D. Graph complete है
उत्तर: A
A: केवल reachable predecessor relax करें।
B: Negative edges शामिल हो सकते हैं।
C: Cycle source से दूर हो सकता है।
D: Complete graph जरूरी नहीं।
P03. s→a=4,s→b=5,a→b=−2: separate-array B_1[b],B_2[b]?
A. 2,2 B. 5,2 C. 5,5 D. ∞,2
उत्तर: B
A: B_1 में two-edge route नहीं।
B: एक edge 5, दो edges पर 4−2=2।
C: दूसरे pass में a से improvement।
D: Direct one-edge route है।
P04. Floyd–Warshall stage k क्या allow करता है?
A. अधिकतम k edges B. Additional internal vertex k C. केवल source k D. Exactly k weight paths
उत्तर: B
A: यह edge-bounded DP है, Floyd नहीं।
B: Internal set में k जुड़ता है।
C: सभी source-target pairs हैं।
D: k vertex index, weight नहीं।
P05. Floyd–Warshall के बाद negative cycle का संकेत?
A. कोई negative off-diagonal B. Negative diagonal entry C. कोई infinite entry D. सभी diagonal zero
उत्तर: B
A: Negative edge बिना cycle भी दे सकता है।
B: D[k,k]<0 negative closed walk है।
C: Infinity unreachable है।
D: Zero diagonal negative cycle संकेत नहीं।
P06. Reachable negative cycle से किन vertices की finite shortest distances नहीं रहतीं?
A. अपने-आप हर vertex B. केवल source C. उस cycle से आगे reachable vertices D. केवल negative outgoing वाले vertices
उत्तर: C
A: अन्य components/upstream unaffected हो सकते हैं।
B: Cycle से source वापस reachable जरूरी नहीं।
C: Cycle repeat करके आगे उन vertices जाएँ।
D: Downstream vertex के outgoing edges न भी हों।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन