Dijkstra: nonnegative weights और settled distances
Contract और संबंध
मौजूदा adjacency representation, BFS/DFS और heap operations उपयोग करें। BFS unweighted graph में edge count minimum करता है, arbitrary weighted sum नहीं। यहाँ directed/undirected graph के weights nonnegative हैं; zero मान्य है। δ(s,v)=source s से v तक minimum path-weight sum; path न हो तो ∞।
1. Tentative distance वास्तविक paths हैं
d[s]=0, बाकी ∞, parents absent रखें। Finite d[u] पर edge (u,v) relax करें: d[u]+w(u,v)<d[v] हो तो distance और parent[v]=u बदलें। हर finite d[v] किसी discovered path की length है, इसलिए shortest distance का upper bound। Code में ∞ को explicitly handle करें; sentinel में जोड़ने से overflow हो सकता है।
Dijkstra minimum tentative distance वाला unsettled u चुनता है। उसका distance ∞ हो तो stop: बाकी unreachable हैं। u settle करें और unsettled neighbors की outgoing edges relax करें। Indexed binary min-heap में key बदलने के लिए decrease-key है। Source का सभी vertices से connected होना जरूरी नहीं।
2. Settlement final क्यों है
Invariant: हर settled vertex की distance true shortest है। अगला minimum u लें और उसके shortest path पर पहला unsettled y तथा settled predecessor x देखें, यदि u source नहीं। x process होने पर relaxation से d[y], y तक path-prefix से बड़ा नहीं। आगे के nonnegative edges से यह prefix, u की पूरी shortest distance से बड़ा नहीं। Minimum choice से d[u]<=d[y]<=δ(s,u)। Actual-path upper bound के कारण d[u]>=δ(s,u), अतः बराबर। Nonnegative weights इसी step में जरूरी हैं।
3. Improvement वाला trace
Directed edges s→a=4,s→b=1,b→a=2,a→t=1,b→t=7। s settle: a=4,b=1,t=∞। b settle: a=3,t=8। a settle: t=4। फिर t settle। Final (s,b,a,t)=(0,1,3,4); parents b←s,a←b,t←a। t से backward parents लेकर reverse करें: s,b,a,t। Direct s→a shortest route में नहीं।
Ties किसी क्रम में process कर सकते हैं; zero edges/equal alternatives से multiple shortest paths हो सकते हैं। इस सरल implementation में parent केवल strict improvement पर बदलें और settled vertex overwrite न करें। इससे अनावश्यक equal-distance rewrites नहीं होते और reconstruction tree स्पष्ट रहता है।
4. Negative-edge counterexample
s→a=2,s→b=5,b→a=−4। Dijkstra a को 2 पर b से पहले settle करेगा, लेकिन true distance b के रास्ते 1 है। Negative cycle भी नहीं; एक negative edge general proof तोड़ सकता है। कुछ negative-edge inputs संयोग से सही हों तो guarantee नहीं बनती। उपयुक्त स्थिति में अगला Bellman–Ford पाठ उपयोग करें।
5. Queue के अनुसार complexity
Adjacency matrix और हर minimum के लिए V scan: O(V²) time, graph storage छोड़कर O(V) arrays। Adjacency lists और indexed binary heap: O((V+E) log V) time, graph के O(V+E) storage के अलावा O(V) auxiliary queue/arrays। Lazy heap में हर improvement पर नया (distance,vertex) push होता है; pop पर d[v] से अलग stale pair या already settled vertex छोड़ें। O(E+1) entries संभव हैं; initialization तथा reachable relaxation मिलाकर O(V+(E+1) log(E+2)) time bound है। अपने implementation का bound बताएँ, automatic decrease-key bound न दें।
Target settle होने पर early stop सही; पहली discovery पर नहीं। Dijkstra distance path sum है, Prim key single connecting-edge weight। Shortest-path tree का अपना total edge weight सभी spanning trees में minimum जरूरी नहीं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Standard Dijkstra guarantee में कौन-से weights मान्य?
A. केवल strictly positive B. Nonnegative, zero सहित C. Cycle न हो तो कोई negative D. बिना शर्त सभी real weights
उत्तर: B
A: Zero weights मान्य हैं।
B: Nonnegative suffix settlement proof देता है।
C: Cycle बिना भी एक negative edge गलत कर सकता है।
D: Weight restriction जरूरी है।
P02. हल किए s,a,b,t graph में t की shortest distance?
A. 4 B. 5 C. 8 D. ∞
उत्तर: A
A: s→b→a→t =1+2+1=4।
B: Direct a route 5, कम अच्छा।
C: b→t वाला route 8।
D: t reachable है।
P03. एक target के लिए safe early stop कब?
A. पहली discovery B. Minimum tentative के रूप में settled C. Adjacency list में पहली बार दिखे D. कोई finite parent मिले
उत्तर: B
A: बाद का route improve कर सकता है।
B: Invariant distance final सिद्ध करता है।
C: नाम आने से distance तय नहीं।
D: Finite path suboptimal हो सकता है।
P04. s→a=2,s→b=5,b→a=−4 में a का true shortest distance?
A. −4 B. 1 C. 2 D. 5
उत्तर: B
A: Source से b cost छूटा।
B: b से 5−4=1।
C: यह direct edge, optimum नहीं।
D: यह b की distance है।
P05. Indexed binary heap और adjacency lists का time:
A. O(V+E) always B. O((V+E) log V) C. O(V²E) necessarily D. O(log V) total
उत्तर: B
A: Heap operations logarithmic factor जोड़ते हैं।
B: V extractions और E तक updates।
C: यह standard bound नहीं।
D: कई vertices/edges process होंगे।
P06. Settlement से पहले finite tentative d[v] क्या है?
A. हमेशा true distance से कम B. Discovered-path upper bound C. हमेशा final D. MST connecting-edge weight
उत्तर: B
A: यह actual path की length है।
B: Shortest path discovered path से लंबा नहीं।
C: Settlement से पहले घट सकता है।
D: यह Prim key है, d[v] नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन