प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम
heapq का उपयोग करके Dijkstra लागू कीजिए, भारित ग्राफ पर रिलैक्सेशन चरणों को ट्रेस कीजिए और cheapest-flights-within-k-stops हल कीजिए।
प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
भारित ग्राफ में सबसे छोटा पथ
डिज्क्स्ट्रा की कलनविधि एकल स्रोत नोड से अन्य सभी नोडों तक का सबसे छोटा पथ गैर-ऋणात्मक किनारा भार वाले भारित ग्राफ में खोजती है। यह वर्तमान में ज्ञात सर्वोत्तम दूरी के क्रम में नोडों को लोभपूर्वक संसाधित करके काम करती है — हर बार सबसे निकट, अभी तक न देखे गए नोड का विस्तार करती है। मुख्य डेटा संरचना एक न्यूनतम-हीप (प्राथमिकता कतार) है, जो सबसे छोटी दूरी वाले नोड को कुशलता से प्राप्त करती है।
कलनविधि के चरणों का अवलोकन
डिज्क्स्ट्रा की कलनविधि: (1) dist[source] = 0 और dist[all others] = inf प्रारंभ करें। (2) (0, source) को न्यूनतम-हीप में डालें। (3) सबसे छोटी दूरी वाले नोड u को निकालें। यदि उसे पहले ही कम दूरी के साथ देखा जा चुका है, तो उसे छोड़ दें। (4) u के प्रत्येक पड़ोसी v के लिए: यदि dist[u] + weight(u,v) < dist[v], तो dist[v] को अद्यतन करें और (dist[v], v) को हीप में डालें। (5) हीप खाली होने तक दोहराएँ।
heapq के साथ पाइथन कार्यान्वयन
पाइथन का heapq एक न्यूनतम-हीप लागू करता है। हम ग्राफ को आसन्नता सूची के रूप में प्रस्तुत करते हैं: graph[u] = [(v, weight), ...]। हीप में (distance, node) युग्म रखे जाते हैं। पुरानी हीप प्रविष्टियों को छोड़ने के लिए हम visited सेट का उपयोग करते हैं — ये वे प्रविष्टियाँ हैं जिन्हें बेहतर पथ मिलने से पहले हीप में डाला गया था।
import heapq
def dijkstra(graph, source):
n = len(graph)
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)] # (distance, node)
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distहल किया हुआ उदाहरण
5 नोड वाले एक ग्राफ पर विचार करें, जिसकी किनारे हैं: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3)। नोड 0 से सबसे छोटे पथ: 1 तक 0→2→1 के रास्ते की लागत 3, 2 तक की लागत 1, 3 तक 0→2→1→3 के रास्ते की लागत 4, और 4 तक 0→2→1→3→4 के रास्ते की लागत 7 है। डिज्क्स्ट्रा इन सभी को एक ही चरण में खोजती है, केवल किसी एक लक्ष्य तक का पथ नहीं।
import heapq
def dijkstra(graph, source):
dist = [float('inf')] * len(graph)
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = [
[(1,4),(2,1)], # 0
[(3,1)], # 1
[(1,2),(3,5)], # 2
[(4,3)], # 3
[] # 4
]
print(dijkstra(graph, 0)) # [0, 3, 1, 4, 7]ऋणात्मक भारों पर डिज्क्स्ट्रा क्यों विफल होता है
डिज्क्स्ट्रा की शुद्धता इस तथ्य पर निर्भर करती है कि जब किसी नोड को न्यूनतम ढेर से निकाला जाता है, तो उसकी दूरी अंतिम होती है। यह केवल तभी सही होता है जब किनारों के भार गैर-ऋणात्मक हों। भार -5 वाले u→v जैसे किसी ऋणात्मक किनारे के साथ, v पर जाने के बाद हमें u से होकर जाने वाला कोई छोटा पथ मिल सकता है — लेकिन v को पहले ही देखा हुआ चिह्नित किया जा चुका है। एक अकेला ऋणात्मक किनारा बाद की सभी दूरी-गणनाओं को अमान्य कर सकता है।
K ठहरावों के भीतर सबसे सस्ती उड़ानें (LeetCode 787)
यह समस्या एक बाधा जोड़ती है: अधिकतम k ठहराव। मानक डिज्क्स्ट्रा चरणों की संख्या को मूल रूप से संभाल नहीं पाता। समाधान यह है कि स्थिति को (cost, node, stops_remaining) तक विस्तृत किया जाए। इस तीन-तत्वीय संरचना के साथ डिज्क्स्ट्रा का उपयोग करें, या k+1 शिथिलीकरण दौरों के साथ बेलमैन-फोर्ड का उपयोग करें। संशोधित डिज्क्स्ट्रा तब रुक जाता है जब बचे हुए ठहराव 0 तक पहुँच जाते हैं, जिससे आगे की छलाँगें रुक जाती हैं।
import heapq
from collections import defaultdict
def findCheapestPrice(n, flights, src, dst, k):
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
heap = [(0, src, k + 1)] # (cost, node, hops_left)
visited = {} # node -> min hops_left seen at this cost level
while heap:
cost, node, hops = heapq.heappop(heap)
if node == dst:
return cost
if hops == 0:
continue
if visited.get(node, 0) >= hops:
continue
visited[node] = hops
for nxt, w in graph[node]:
heapq.heappush(heap, (cost + w, nxt, hops - 1))
return -1
print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200समय जटिलता का विश्लेषण
द्विआधारी ढेर के साथ, डिज्क्स्ट्रा O((V + E) log V) समय में चलता है: प्रत्येक शीर्ष को एक बार निकाला जाता है (V निष्कासन), प्रत्येक किनारा एक बार डालने की क्रिया करवा सकता है (E डालने की क्रियाएँ), और ढेर की प्रत्येक क्रिया की लागत O(log V) होती है। फिबोनाची ढेर के साथ सीमा O(E + V log V) तक बेहतर हो जाती है, लेकिन पाइथन का heapq एक द्विआधारी ढेर है। विरल ग्राफ़ों (E ≈ V) के लिए द्विआधारी ढेर वाला संस्करण O(V log V) है; सघन ग्राफ़ों (E ≈ V²) के लिए यह O(V² log V) है।
सबसे छोटे पथ का पुनर्निर्माण
वास्तविक पथ (केवल दूरियाँ नहीं) प्राप्त करने के लिए एक prev सारणी बनाए रखें: dist[v] को अद्यतन करते समय prev[v] = u सेट करें। एल्गोरिदम पूरा होने के बाद, पीछे की ओर संकेतकों का अनुसरण करके स्रोत से गंतव्य तक का पथ पुनर्निर्मित करें: dst से शुरू करें, prev संकेतकों का अनुसरण करते हुए source तक जाएँ और परिणाम को उलट दें।
import heapq
def dijkstra_path(graph, source, target):
n = len(graph)
dist = [float('inf')] * n
prev = [-1] * n
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited: continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct
path, node = [], target
while node != -1:
path.append(node)
node = prev[node]
return dist[target], path[::-1]विरल ग्राफ़ों के लिए शब्दकोश का उपयोग
जब नोड पाठ-श्रृंखलाएँ या असन्निकट पूर्णांक हों, तो सन्निकटता सूची के लिए defaultdict(list) और दूरियों के लिए सामान्य dict का उपयोग करें। यह LeetCode की नेटवर्क विलंब समय जैसी समस्याओं में आम है, जहाँ नोडों को 1 से n तक अंकित किया जाता है। dist = {node: inf for node in all_nodes} का उपयोग करना याद रखें और एल्गोरिदम के बाद अभिगम्य न होने वाले नोडों की जाँच करें।
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2भाररहित ग्राफ़ों के लिए BFS से तुलना
भाररहित ग्राफ़ों के लिए BFS, O(V + E) में सबसे छोटे पथ खोजता है — यह डिज्क्स्ट्रा के O((V+E) log V) से तेज़ है। डिज्क्स्ट्रा सामान्य FIFO कतार के बजाय प्राथमिकता कतार का उपयोग करके BFS को भारित ग्राफ़ों तक विस्तृत करता है। जब सभी किनारों के भार समान होते हैं, तो डिज्क्स्ट्रा BFS में बदल जाता है। भाररहित ग्राफ़ों के लिए BFS, गैर-ऋणात्मक भारों के लिए डिज्क्स्ट्रा और ऋणात्मक भारों के लिए बेलमैन-फोर्ड चुनें।
घटती-कुंजी अनुकूलन के साथ डिज्क्स्ट्रा
पाठ्यपुस्तक वाला डिज्क्स्ट्रा घटती-कुंजी वाली प्राथमिकता कतार का उपयोग करता है: जब किसी नोड की दूरी बेहतर होती है, तो उसकी प्राथमिकता वहीं पर अद्यतन की जाती है। इसके लिए O(E + V log V) प्राप्त करने हेतु फिबोनाची ढेर चाहिए, लेकिन इसे लागू करना कठिन है। साक्षात्कारों में उपयोग किया जाने वाला विलंबित विलोपन तरीका इसके बजाय एक नई प्रविष्टि डालता है और पुरानी निकासी को छोड़ देता है — यह केवल स्थिर गुणक जितने अतिरिक्त खर्च के साथ सरल है। पाइथन में heapq के साथ विलंबित विलोपन, साक्षात्कारों में मानक कार्यान्वयन है।
त्वरित जाँच
इस पाठ में सिखाई गई डेटा संरचनाएँ एवं एल्गोरिदम — कोडिंग इंटरव्यू तैयारी की अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: डिज्क्स्ट्रा वर्तमान सर्वोत्तम दूरी के क्रम में नोडों को लालच से संसाधित करने के लिए न्यूनतम ढेर का उपयोग करता है, यह O((V+E) log V) समय में चलता है और ऋणात्मक-भार वाले किनारों पर विफल होता है, और निकासी के समय देखे गए नोडों के समुच्चय की जाँच करके पुरानी ढेर प्रविष्टियों को संभाला जाता है। आगे हम बेलमैन-फोर्ड पढ़ेंगे, जो n-1 शिथिलीकरण दौरों के माध्यम से ऋणात्मक भारों को संभालता है।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम” पाठ निःशुल्क है?
हाँ—“प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम” में मैं क्या सीखूँगा?
heapq का उपयोग करके Dijkstra लागू कीजिए, भारित ग्राफ पर रिलैक्सेशन चरणों को ट्रेस कीजिए और cheapest-flights-within-k-stops हल कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- प्राथमिकता कतार के साथ Dijkstra एल्गोरिदम
- Bellman-Ford और ऋणात्मक चक्र
- Floyd-Warshall: सभी युग्मों के सबसे छोटे पथ
- नेटवर्क विलंब समय और पथ पुनर्निर्माण