Python में Dijkstra एल्गोरिद्म का इम्प्लीमेंटेशन: चरण-दर-चरण ट्यूटोरियल
Dijkstra का एल्गोरिद्म किसी नेटवर्क में दो बिंदुओं के बीच सबसे छोटा मार्ग खोजने में मदद करता है—जैसे मानचित्र पर सबसे तेज़ रास्ता ढूँढना—जो दूरी को चरण-दर-चरण जाँचता और अपडेट करता चलता है।
Dijkstra’s नेटवर्क में दो बिंदुओं के बीच सबसे छोटा पथ खोजने के लिए सबसे अधिक इस्तेमाल होने वाला एल्गोरिद्म है, जिसके कई उपयोग हैं। यह कंप्यूटर विज्ञान और ग्राफ थ्योरी में बुनियादी है। इसे समझना और इम्प्लीमेंट करना सीखना उन्नत ग्राफ एल्गोरिद्म और उनके अनुप्रयोगों के लिए रास्ता खोलता है।
यह अपने greedy एल्गोरिद्म दृष्टिकोण के माध्यम से एक मूल्यवान समस्या-समाधान तरीका भी सिखाता है, जिसमें वर्तमान जानकारी के आधार पर हर कदम पर सर्वोत्तम विकल्प चुना जाता है।
यह कौशल अन्य optimization एल्गोरिद्म पर भी लागू होता है। Dijkstra’s एल्गोरिद्म हर स्थिति में सबसे कुशल नहीं हो सकता, लेकिन “सबसे कम दूरी” जैसी समस्याएँ हल करते समय यह एक अच्छा बेसलाइन साबित हो सकता है।
उदाहरण शामिल हैं:
GPS नेविगेशन सिस्टम सबसे तेज़ मार्ग ढूंढना
कंप्यूटर नेटवर्क में डेटा पैकेट की रूटिंग
डिलीवरी सेवाएँ दक्षता के लिए रूट का अनुकूलन
सोशल नेटवर्क (कनेक्शन सुझाना)
वित्त (सर्वोत्तम निवेश पथ खोजना)
प्रोजेक्ट प्रबंधन (सबसे कुशल वर्कफ़्लो खोजना)
भले ही आपको इनमें से किसी चीज़ में रुचि न हो, Python में Dijkstra’s एल्गोरिद्म इम्प्लीमेंट करना आपको इन महत्वपूर्ण अवधारणाओं का अभ्यास करने देगा:
Python में Dijkstra’s एल्गोरिद्म इम्प्लीमेंट करने के लिए, हमें ग्राफ थ्योरी की कुछ बुनियादी अवधारणाएँ दोहरानी होंगी। सबसे पहले, हमारे पास ग्राफ होते हैं:
ग्राफ नोड (वर्टेक्स) के समूह होते हैं जो एज से जुड़े होते हैं। नोड नेटवर्क में इकाइयों या बिंदुओं का प्रतिनिधित्व करते हैं, जबकि एज उनके बीच के संबंधों या कनेक्शन का प्रतिनिधित्व करते हैं।
ग्राफ weighted या unweighted हो सकते हैं। Unweighted ग्राफ में सभी एज का वज़न समान होता है (अक्सर 1 रखा जाता है)। Weighted ग्राफ में (जैसा आप समझ ही गए), प्रत्येक एज के साथ एक वज़न जुड़ा होता है, जो अक्सर लागत, दूरी, या समय दर्शाता है।
हम इस ट्यूटोरियल में weighted ग्राफ का उपयोग करेंगे क्योंकि Dijkstra’s एल्गोरिद्म के लिए उनकी आवश्यकता होती है।
ग्राफ में एक path का अर्थ है एज द्वारा जुड़े नोड्स का क्रम, जो किसी विशेष नोड से शुरू होकर किसी अन्य पर समाप्त होता है। इस ट्यूटोरियल में हमारा ध्यान सबसे छोटे पथ पर है—वह पथ जिसका कुल वज़न (दूरी, लागत, आदि) न्यूनतम हो।
Dijkstra’s एल्गोरिद्म: दृश्य रूप में समझाया गया
ट्यूटोरियल के शेष हिस्से के लिए, हम वही अंतिम ग्राफ उपयोग करेंगे जो हमने देखा था:
आइए Dijkstra’s एल्गोरिद्म का उपयोग करके B और F के बीच सबसे छोटा पथ ढूँढें—कम से कम सात संभावित पथों में से। शुरुआत में, हम यह काम दृश्य रूप से करेंगे और बाद में कोड में इम्प्लीमेंट करेंगे।
सबसे पहले, हम एल्गोरिद्म को इस प्रकार initialize करते हैं:
हम B को root (source) नोड मानते हैं।
हम B और अन्य सभी नोड्स के बीच की दूरी को आरंभिक, tentative वैल्यू के रूप में अनंत (infinity) सेट करते हैं। B के लिए मान 0 रखते हैं क्योंकि यह स्वयं तक की दूरी है:
फिर, हम निम्नलिखित चरणों को बार-बार दोहराते हैं:
सबसे छोटे मान वाले नोड को “current node” चुनें और उसके सभी पड़ोसी नोड्स पर जाएँ। हर पड़ोसी पर जाते समय, उनके tentative मान infinity से बदलकर source से उस एज के वज़न के अनुसार अपडेट करें।
जब current node के सभी पड़ोसी देख लिए जाएँ, तो current node को “visited” चिह्नित करें। एक बार कोई नोड “visited” हो जाए, तो उसका मान target तक के सबसे छोटे पथ का मान होता है।
एल्गोरिद्म चरण 1 पर लौटता है और सबसे छोटे मान वाले अगले नोड को चुनता है।
हमारे ग्राफ में B के तीन पड़ोसी हैं — A, D, और E। root नोड से शुरू करते हुए, प्रत्येक पर जाएँ और उनके मान (iteration 1) एज वेट्स के आधार पर अपडेट करें:
Iteration 2 में, हम फिर सबसे छोटे मान वाले नोड को चुनते हैं—इस बार E। इसके पड़ोसी C, D, और G हैं। B को छोड़ देते हैं क्योंकि हम पहले ही उसे visit कर चुके हैं। आइए E के पड़ोसियों के मान अपडेट करें:
हम C का मान 5.6 सेट करते हैं क्योंकि उसका मान B से C तक के वज़नों के संचयी योग के बराबर है। G के लिए भी यही लागू होता है। हालाँकि, आप देखें तो D का मान 3.5 ही रहता है, जबकि अन्य नोड्स की तरह उसे 3.5 + 2.8 = 6.3 होना चाहिए था।
नियम यह है कि यदि नया संचयी योग नोड के वर्तमान मान से बड़ा है, तो हम उसे अपडेट नहीं करेंगे, क्योंकि नोड पहले से ही root तक की सबसे कम दूरी दिखा रहा है। इस मामले में, D का वर्तमान मान 3.5 पहले से ही B तक की सबसे कम दूरी बताता है क्योंकि वे पड़ोसी हैं।
हम इसी तरह आगे बढ़ते हैं जब तक कि सभी नोड्स visit न हो जाएँ। जब यह हो जाता है, तब हमारे पास B से प्रत्येक नोड तक की सबसे कम दूरी होगी और हम बस B से F तक का मान देख सकते हैं।
संक्षेप में, चरण इस प्रकार हैं:
ग्राफ को source नोड के लिए 0 और अन्य सभी नोड्स के लिए infinity से initialize करें। source को “current node” के रूप में शुरू करें।
current node के सभी पड़ोसियों पर जाएँ और उनके मान source से वज़नों (दूरी) के संचयी योग के अनुसार अपडेट करें। यदि किसी पड़ोसी का वर्तमान मान संचयी योग से छोटा है, तो वही बना रहता है। “current node” को समाप्त (finished) चिह्नित करें।
अधूरा (unfinished) सबसे छोटे मान वाला नोड “current node” बनाएं।
चरण 2 और 3 को तब तक दोहराएँ जब तक सभी नोड्स समाप्त न हो जाएँ।
Python में Dijkstra एल्गोरिद्म का चरण-दर-चरण इम्प्लीमेंटेशन
अब, आपकी समझ पुख्ता करने के लिए, हम Dijkstra’s एल्गोरिद्म को Python में चरण-दर-चरण इम्प्लीमेंट करना सीखेंगे।
डिक्शनरी के रूप में ग्राफ समझना
सबसे पहले, हमें Python में ग्राफ को प्रस्तुत करने का तरीका चाहिए—सबसे लोकप्रिय विकल्प है dictionary का उपयोग करना। यदि हमारा ग्राफ यह है:
हम इसे निम्नलिखित डिक्शनरी से दर्शा सकते हैं:
graph ={"A":{"B":3,"C":3},"B":{"A":3,"D":3.5,"E":2.8},"C":{"A":3,"E":2.8,"F":3.5},"D":{"B":3.5,"E":3.1,"G":10},"E":{"B":2.8,"C":2.8,"D":3.1,"G":7},"F":{"G":2.5,"C":3.5},"G":{"F":2.5,"E":7,"D":10},}संचालित द्वारा
डिक्शनरी की प्रत्येक कुंजी एक नोड होती है और प्रत्येक मान एक डिक्शनरी होती है जिसमें उस कुंजी के पड़ोसी और उनके तक की दूरियाँ होती हैं। हमारे ग्राफ में सात नोड हैं, जिसका अर्थ है डिक्शनरी में सात कुंजियाँ होनी चाहिए।
अन्य स्रोत ऊपर दी गई डिक्शनरी को अक्सर adjacency list डिक्शनरी कहते हैं। अब से हम भी इसी शब्द का उपयोग करेंगे।
1. एक Graph क्लास बनाना
अपने कोड को अधिक मॉड्यूलर और समझने में आसान बनाने के लिए, हम ग्राफ को दर्शाने हेतु एक सरल Graph क्लास इम्प्लीमेंट करेंगे। अंदरूनी तौर पर, यह adjacency list डिक्शनरी का उपयोग करेगा। इसमें दो नोड्स के बीच आसानी से कनेक्शन जोड़ने की एक मेथड भी होगी:
classGraph:def__init__(self, graph:dict={}):
self.graph = graph # A dictionary for the adjacency listdefadd_edge(self, node1, node2, weight):if node1 notin self.graph:# Check if the node is already added
self.graph[node1]={}# If not, create the node
self.graph[node1][node2]= weight # Else, add a connection to its neighborसंचालित द्वारा
इस क्लास का उपयोग करके, हम अपना ग्राफ इस तरह से शुरुआती अवस्था से क्रमशः बना सकते हैं:
G = Graph()# Add A and its neighbors
G.add_edge("A","B",3)
G.add_edge("A","C",3)# Add B and its neighbors
G.add_edge("B","A",3)
G.add_edge("B","D",3.5)
G.add_edge("B","E",2.8)...संचालित द्वारा
या हम सीधे adjacency list डिक्शनरी पास कर सकते हैं, जो तेज़ तरीका है:
# Use the dictionary we defined earlier
G = Graph(graph=graph)
G.graph
संचालित द्वारा
2. source से दूरी संग्रहीत करने के लिए डिक्शनरी का उपयोग
हम एल्गोरिद्म के लिए—इस बार—एक और क्लास मेथड बनाते हैं: shortest_distances:
classGraph:def__init__(self, graph:dict={}):
self.graph = graph
# The add_edge method omitted for spacedefshortest_distances(self, source:str):# Initialize the values of all nodes with infinity
distances ={node:float("inf")for node in self.graph}
distances[source]=0# Set the source value to 0...संचालित द्वारा
मेथड के अंदर हम सबसे पहले एक डिक्शनरी परिभाषित करते हैं जिसमें नोड-वैल्यू जोड़े होते हैं। यह डिक्शनरी हर बार तब अपडेट होती है जब हम किसी नोड और उसके पड़ोसियों पर जाते हैं। जैसा कि हमने एल्गोरिद्म के दृश्य विवरण में बताया, सभी नोड्स के आरंभिक मान infinity होते हैं, जबकि source का मान 0 होता है।
जब हम मेथड लिखना पूरा कर लेंगे, तो यह डिक्शनरी रिटर्न की जाएगी और इसमें source से सभी नोड्स तक की सबसे कम दूरियाँ होंगी। हम B से F तक की दूरी इस तरह से पा सकेंगे:
# Sneak-peek - find the shortest paths from B
distances = G.shortest_distances("B")
to_F = distances["F"]print(f"The shortest distance from B to F is {to_F}")संचालित द्वारा
3. नोड्स पर iterate करने के लिए priority queue का उपयोग
अब, हमें Dijkstra के नियमों के अनुसार ग्राफ नोड्स पर लूप करने का एक तरीका चाहिए। याद करें, हर iteration में हमें सबसे छोटे मान वाले नोड को चुनकर उसके पड़ोसियों पर जाना होता है।
आप कह सकते हैं कि हम साधारण रूप से डिक्शनरी की keys पर लूप चला सकते हैं:
यह तरीका काम नहीं करेगा क्योंकि यह हमें नोड्स को उनके मान के आधार पर sort करने का तरीका नहीं देता। इसलिए, साधारण arrays पर्याप्त नहीं होंगी। इस हिस्से की समस्या सुलझाने के लिए हम priority queue नाम की चीज़ का उपयोग करेंगे।
एक priority queue बिल्कुल सामान्य लिस्ट (array) जैसी होती है, लेकिन इसके प्रत्येक तत्व के साथ उनकी प्राथमिकता दर्शाने के लिए एक अतिरिक्त मान होता है। यह रही एक नमूना priority queue:
इस queue में तीन तत्व हैं — A, C, और D — और इन सबका एक प्राथमिकता मान है जो queue पर होने वाले ऑपरेशनों को निर्धारित करता है। Python priority queues के साथ काम करने के लिए बिल्ट-इन heapq लाइब्रेरी प्रदान करता है:
from heapq import heapify, heappop, heappushसंचालित द्वारा
लाइब्रेरी में तीन फ़ंक्शन हैं जिनकी हमें परवाह है:
heapify: प्राथमिकता-मूल्य जोड़ों वाले tuples की लिस्ट को priority queue में बदल देता है।
heappush: किसी तत्व को उसकी प्राथमिकता के साथ queue में जोड़ता है।
heappop: सबसे अधिक प्राथमिकता वाले तत्व (सबसे छोटे मान वाले तत्व) को हटाकर लौटाता है।
pq =[(3,"A"),(1,"C"),(7,"D")]# Convert into a queue object
heapify(pq)# Return the highest priority value
heappop(pq)संचालित द्वारा
queue नए तत्व की प्राथमिकता के आधार पर सही तरीके से अपडेट हो गई क्योंकि heappop ने 0 प्राथमिकता वाले नए तत्व को लौटाया।
ध्यान दें कि किसी आइटम को pop करने के बाद वह queue का हिस्सा नहीं रहता।
अब, अपने एल्गोरिद्म पर वापस आते हैं, distances initialize करने के बाद, हम एक नई priority queue बनाते हैं जिसमें शुरू में केवल source नोड होता है:
classGraph:def__init__(self, graph:dict={}):
self.graph = graph
defshortest_distances(self, source:str):# Initialize the values of all nodes with infinity
distances ={node:float("inf")for node in self.graph}
distances[source]=0# Set the source value to 0# Initialize a priority queue
pq =[(0, source)]
heapify(pq)# Create a set to hold visited nodes
visited =set()संचालित द्वारा
pq के प्रत्येक तत्व की प्राथमिकता उसका वर्तमान मान होगा। हम visited नोड्स को रिकॉर्ड करने के लिए एक खाली set भी initialize करते हैं।
4. while लूप के रूप में Dijkstra एल्गोरिद्म
अब हम एक while लूप का उपयोग करके सभी unvisited नोड्स पर iterate करना शुरू करते हैं:
classGraph:def__init__(self, graph:dict={}):
self.graph = graph
defshortest_distances(self, source:str):# Initialize the values of all nodes with infinity
distances ={node:float("inf")for node in self.graph}
distances[source]=0# Set the source value to 0# Initialize a priority queue
pq =[(0, source)]
heapify(pq)# Create a set to hold visited nodes
visited =set()while pq:# While the priority queue isn't empty
current_distance, current_node = heappop(
pq
)# Get the node with the min distanceif current_node in visited:continue# Skip already visited nodes
visited.add(current_node)# Else, add the node to visited setसंचालित द्वारा
जब तक priority queue खाली नहीं हो जाती, हम सबसे अधिक प्राथमिकता (न्यूनतम मान) वाले नोड को pop करते रहते हैं और उसके मान व नाम को current_distance और current_node में निकालते हैं। यदि current_nodevisited में है, तो उसे छोड़ देते हैं। अन्यथा, उसे visited चिह्नित करते हैं और फिर उसके पड़ोसियों पर जाते हैं:
while pq:# While the priority queue isn't empty
current_distance, current_node = heappop(pq)if current_node in visited:continue
visited.add(current_node)for neighbor, weight in self.graph[current_node].items():# Calculate the distance from current_node to the neighbor
tentative_distance = current_distance + weight
if tentative_distance < distances[neighbor]:
distances[neighbor]= tentative_distance
heappush(pq,(tentative_distance, neighbor))return distances
संचालित द्वारा
प्रत्येक पड़ोसी के लिए, हम current नोड से tentative दूरी उसकी एज के वज़न को जोड़कर निकालते हैं। फिर जांचते हैं कि यह दूरी distances में उस पड़ोसी की दूरी से छोटी है या नहीं। यदि हाँ, तो हम distances डिक्शनरी अपडेट करते हैं और पड़ोसी को उसकी tentative दूरी के साथ priority queue में जोड़ देते हैं।
बस! हमने Dijkstra का एल्गोरिद्म इम्प्लीमेंट कर लिया। आइए इसे परखें:
G = Graph(graph)
distances = G.shortest_distances("B")print(distances,"\n")
to_F = distances["F"]print(f"The shortest distance from B to F is {to_F}")संचालित द्वारा
{'A':3,'B':0,'C':5.6,'D':3.5,'E':2.8,'F':9.1,'G':9.8}
The shortest distance from B to F is9.1संचालित द्वारा
तो, B से F की दूरी 9.1 है। लेकिन ठहरिए: यह पथ कौन-सा है?
5. सबसे छोटा पथ बनाना
तो, फिलहाल हमारे पास सबसे छोटी दूरियाँ हैं, पथ नहीं—जिससे हमारा ग्राफ कुछ इस तरह दिखता है:
गणना की गई सबसे छोटी दूरी से सबसे छोटा पथ बनाने के लिए, हम target से अपने कदमों को पिछड़ी दिशा में ट्रेस कर सकते हैं। F से जुड़ी प्रत्येक एज के लिए, हम उसका वज़न घटाते हैं:
9.1–3.5 = 5.6
9.1–2.5 = 6.5
फिर देखते हैं कि क्या परिणामों में से कोई F के पड़ोसियों के मान से मेल खाता है। केवल 5.6, C के मान से मेल खाता है, जिसका मतलब है कि C सबसे छोटे पथ का हिस्सा है।
हम यही प्रक्रिया C के पड़ोसी A और E के लिए दोहराते हैं:
5.6–3 = 2.6
5.6–2.8 = 2.8
चूँकि 2.8 E के मान से मेल खाता है, यह सबसे छोटे पथ का हिस्सा है। E, B का भी पड़ोसी है, जो B और F के बीच सबसे छोटे पथ को BECF बनाता है।
आइए इस प्रक्रिया का इम्प्लीमेंटेशन अपनी क्लास में जोड़ें। कोड ऊपर दिए गए विवरण से थोड़ा अलग है क्योंकि यह B और सभी अन्य नोड्स के बीच के सबसे छोटे पथ ढूँढता है, केवल F के नहीं।
साथ ही, यह इसे उलटी दिशा में करता है, पर मूल विचार वही है।
निम्नलिखित कोड की पंक्तियाँ shortest_distances मेथड के अंत में जोड़ें और पुराना return स्टेटमेंट हटा दें:
predecessors ={node:Nonefor node in self.graph}for node, distance in distances.items():for neighbor, weight in self.graph[node].items():if distances[neighbor]== distance + weight:
predecessors[neighbor]= node
return distances, predecessors
संचालित द्वारा
जब कोड चलता है, तो predecessors डिक्शनरी में प्रत्येक नोड का तात्कालिक parent होता है जो source तक के सबसे छोटे पथ में आता है। आइए इसे आज़माएँ:
G = Graph(graph)
distances, predecessors = G.shortest_distances("B")print(predecessors)संचालित द्वारा
{'A':'B','B':None,'C':'E','D':'B','E':'B','F':'C','G':'E'}संचालित द्वारा
पहले, आइए predecessors डिक्शनरी का उपयोग करते हुए F से backtrack करके सबसे छोटा पथ manually ढूँढें:
# Check the predecessor of F
predecessors["F"]संचालित द्वारा
लीजिए! डिक्शनरी हमें सही बताती है कि B और F के बीच सबसे छोटा पथ BECF है।
लेकिन हमने यह तरीका आंशिक रूप से manual अपनाया। हम ऐसी मेथड चाहते हैं जो किसी भी source से किसी भी target तक predecessors डिक्शनरी से बना सबसे छोटा पथ स्वतः लौटा दे। हम इस मेथड को shortest_path के रूप में परिभाषित करते हैं (इसे क्लास के अंत में जोड़ें):
defshortest_path(self, source:str, target:str):# Generate the predecessors dict
_, predecessors = self.shortest_distances(source)
path =[]
current_node = target
# Backtrack from the target node using predecessorswhile current_node:
path.append(current_node)
current_node = predecessors[current_node]# Reverse the path and return it
path.reverse()return path
संचालित द्वारा
shortest_distances फ़ंक्शन का उपयोग करके हम predecessors डिक्शनरी बनाते हैं। फिर, हम एक while लूप शुरू करते हैं जो हर iteration में current नोड से उसके parent पर जाता है जब तक source नोड न आ जाए। इसके बाद, हम सूची को reverse करके लौटाते हैं, जिसमें source से target तक का पथ होता है।
इस ट्यूटोरियल में, हमने ग्राफ थ्योरी के सबसे बुनियादी एल्गोरिद्म में से एक—Dijkstra’s—सीखा। यह ग्राफ-सदृश संरचनाओं में दो बिंदुओं के बीच सबसे छोटा पथ खोजने के लिए अक्सर पहला विकल्प होता है। अपनी सादगी के कारण, इसके कई उद्योगों में अनुप्रयोग हैं, जैसे:
लॉजिस्टिक्स और परिवहन
नेटवर्किंग और दूरसंचार
मैन्युफैक्चरिंग और रोबोटिक्स
वित्त और निवेश
नगर नियोजन
मुझे उम्मीद है कि Python में Dijkstra’s एल्गोरिद्म का इम्प्लीमेंटेशन आपको ग्राफ एल्गोरिद्म की अद्भुत दुनिया में रुचि जगाने में सफल रहा। यदि आप और सीखना चाहते हैं, तो मैं निम्नलिखित संसाधनों की दृढ़ता से सिफारिश करता हूँ:
मैं 2 से अधिक वर्षों के अनुभव वाला डेटा साइंस कंटेंट क्रिएटर हूँ और Medium पर सबसे बड़े फॉलोइंग्स में से एक रखता हूँ। मुझे एआई और एमएल पर विस्तार से लेख लिखना पसंद है, जिसमें हल्का-सा व्यंग्यात्मक अंदाज रहता है—क्योंकि कुछ तो करना पड़ता है ताकि वे कम उबाऊ लगें। मैंने 130 से अधिक लेख और एक DataCamp कोर्स तैयार किया है, और एक और बन रहा है। मेरा कंटेंट 50 लाख से अधिक लोगों ने देखा है, जिनमें से 20 हज़ार लोग Medium और LinkedIn पर फॉलोअर्स बन गए।
Dijkstra’s एल्गोरिद्म क्यों सीखें?
Dijkstra’s नेटवर्क में दो बिंदुओं के बीच सबसे छोटा पथ खोजने के लिए सबसे अधिक इस्तेमाल होने वाला एल्गोरिद्म है, जिसके कई उपयोग हैं। यह कंप्यूटर विज्ञान और ग्राफ थ्योरी में बुनियादी है। इसे समझना और इम्प्लीमेंट करना सीखना उन्नत ग्राफ एल्गोरिद्म और उनके अनुप्रयोगों के लिए रास्ता खोलता है।
यह अपने greedy एल्गोरिद्म दृष्टिकोण के माध्यम से एक मूल्यवान समस्या-समाधान तरीका भी सिखाता है, जिसमें वर्तमान जानकारी के आधार पर हर कदम पर सर्वोत्तम विकल्प चुना जाता है।
यह कौशल अन्य optimization एल्गोरिद्म पर भी लागू होता है। Dijkstra’s एल्गोरिद्म हर स्थिति में सबसे कुशल नहीं हो सकता, लेकिन “सबसे कम दूरी” जैसी समस्याएँ हल करते समय यह एक अच्छा बेसलाइन साबित हो सकता है।
उदाहरण शामिल हैं:
भले ही आपको इनमें से किसी चीज़ में रुचि न हो, Python में Dijkstra’s एल्गोरिद्म इम्प्लीमेंट करना आपको इन महत्वपूर्ण अवधारणाओं का अभ्यास करने देगा:
ग्राफ से संबंधित प्रमुख अवधारणाएँ
Python में Dijkstra’s एल्गोरिद्म इम्प्लीमेंट करने के लिए, हमें ग्राफ थ्योरी की कुछ बुनियादी अवधारणाएँ दोहरानी होंगी। सबसे पहले, हमारे पास ग्राफ होते हैं:
ग्राफ नोड (वर्टेक्स) के समूह होते हैं जो एज से जुड़े होते हैं। नोड नेटवर्क में इकाइयों या बिंदुओं का प्रतिनिधित्व करते हैं, जबकि एज उनके बीच के संबंधों या कनेक्शन का प्रतिनिधित्व करते हैं।
ग्राफ weighted या unweighted हो सकते हैं। Unweighted ग्राफ में सभी एज का वज़न समान होता है (अक्सर 1 रखा जाता है)। Weighted ग्राफ में (जैसा आप समझ ही गए), प्रत्येक एज के साथ एक वज़न जुड़ा होता है, जो अक्सर लागत, दूरी, या समय दर्शाता है।
हम इस ट्यूटोरियल में weighted ग्राफ का उपयोग करेंगे क्योंकि Dijkstra’s एल्गोरिद्म के लिए उनकी आवश्यकता होती है।
ग्राफ में एक path का अर्थ है एज द्वारा जुड़े नोड्स का क्रम, जो किसी विशेष नोड से शुरू होकर किसी अन्य पर समाप्त होता है। इस ट्यूटोरियल में हमारा ध्यान सबसे छोटे पथ पर है—वह पथ जिसका कुल वज़न (दूरी, लागत, आदि) न्यूनतम हो।
Dijkstra’s एल्गोरिद्म: दृश्य रूप में समझाया गया
ट्यूटोरियल के शेष हिस्से के लिए, हम वही अंतिम ग्राफ उपयोग करेंगे जो हमने देखा था:
आइए Dijkstra’s एल्गोरिद्म का उपयोग करके B और F के बीच सबसे छोटा पथ ढूँढें—कम से कम सात संभावित पथों में से। शुरुआत में, हम यह काम दृश्य रूप से करेंगे और बाद में कोड में इम्प्लीमेंट करेंगे।
सबसे पहले, हम एल्गोरिद्म को इस प्रकार initialize करते हैं:
फिर, हम निम्नलिखित चरणों को बार-बार दोहराते हैं:
हमारे ग्राफ में B के तीन पड़ोसी हैं — A, D, और E। root नोड से शुरू करते हुए, प्रत्येक पर जाएँ और उनके मान (iteration 1) एज वेट्स के आधार पर अपडेट करें:
Iteration 2 में, हम फिर सबसे छोटे मान वाले नोड को चुनते हैं—इस बार E। इसके पड़ोसी C, D, और G हैं। B को छोड़ देते हैं क्योंकि हम पहले ही उसे visit कर चुके हैं। आइए E के पड़ोसियों के मान अपडेट करें:
हम C का मान 5.6 सेट करते हैं क्योंकि उसका मान B से C तक के वज़नों के संचयी योग के बराबर है। G के लिए भी यही लागू होता है। हालाँकि, आप देखें तो D का मान 3.5 ही रहता है, जबकि अन्य नोड्स की तरह उसे 3.5 + 2.8 = 6.3 होना चाहिए था।
नियम यह है कि यदि नया संचयी योग नोड के वर्तमान मान से बड़ा है, तो हम उसे अपडेट नहीं करेंगे, क्योंकि नोड पहले से ही root तक की सबसे कम दूरी दिखा रहा है। इस मामले में, D का वर्तमान मान 3.5 पहले से ही B तक की सबसे कम दूरी बताता है क्योंकि वे पड़ोसी हैं।
हम इसी तरह आगे बढ़ते हैं जब तक कि सभी नोड्स visit न हो जाएँ। जब यह हो जाता है, तब हमारे पास B से प्रत्येक नोड तक की सबसे कम दूरी होगी और हम बस B से F तक का मान देख सकते हैं।
संक्षेप में, चरण इस प्रकार हैं:
Python में Dijkstra एल्गोरिद्म का चरण-दर-चरण इम्प्लीमेंटेशन
अब, आपकी समझ पुख्ता करने के लिए, हम Dijkstra’s एल्गोरिद्म को Python में चरण-दर-चरण इम्प्लीमेंट करना सीखेंगे।
डिक्शनरी के रूप में ग्राफ समझना
सबसे पहले, हमें Python में ग्राफ को प्रस्तुत करने का तरीका चाहिए—सबसे लोकप्रिय विकल्प है dictionary का उपयोग करना। यदि हमारा ग्राफ यह है:
हम इसे निम्नलिखित डिक्शनरी से दर्शा सकते हैं:
डिक्शनरी की प्रत्येक कुंजी एक नोड होती है और प्रत्येक मान एक डिक्शनरी होती है जिसमें उस कुंजी के पड़ोसी और उनके तक की दूरियाँ होती हैं। हमारे ग्राफ में सात नोड हैं, जिसका अर्थ है डिक्शनरी में सात कुंजियाँ होनी चाहिए।
अन्य स्रोत ऊपर दी गई डिक्शनरी को अक्सर adjacency list डिक्शनरी कहते हैं। अब से हम भी इसी शब्द का उपयोग करेंगे।
1. एक
Graphक्लास बनानाअपने कोड को अधिक मॉड्यूलर और समझने में आसान बनाने के लिए, हम ग्राफ को दर्शाने हेतु एक सरल
Graphक्लास इम्प्लीमेंट करेंगे। अंदरूनी तौर पर, यह adjacency list डिक्शनरी का उपयोग करेगा। इसमें दो नोड्स के बीच आसानी से कनेक्शन जोड़ने की एक मेथड भी होगी:इस क्लास का उपयोग करके, हम अपना ग्राफ इस तरह से शुरुआती अवस्था से क्रमशः बना सकते हैं:
या हम सीधे adjacency list डिक्शनरी पास कर सकते हैं, जो तेज़ तरीका है:
2. source से दूरी संग्रहीत करने के लिए डिक्शनरी का उपयोग
हम एल्गोरिद्म के लिए—इस बार—एक और क्लास मेथड बनाते हैं:
shortest_distances:मेथड के अंदर हम सबसे पहले एक डिक्शनरी परिभाषित करते हैं जिसमें नोड-वैल्यू जोड़े होते हैं। यह डिक्शनरी हर बार तब अपडेट होती है जब हम किसी नोड और उसके पड़ोसियों पर जाते हैं। जैसा कि हमने एल्गोरिद्म के दृश्य विवरण में बताया, सभी नोड्स के आरंभिक मान infinity होते हैं, जबकि source का मान 0 होता है।
जब हम मेथड लिखना पूरा कर लेंगे, तो यह डिक्शनरी रिटर्न की जाएगी और इसमें source से सभी नोड्स तक की सबसे कम दूरियाँ होंगी। हम B से F तक की दूरी इस तरह से पा सकेंगे:
3. नोड्स पर iterate करने के लिए priority queue का उपयोग
अब, हमें Dijkstra के नियमों के अनुसार ग्राफ नोड्स पर लूप करने का एक तरीका चाहिए। याद करें, हर iteration में हमें सबसे छोटे मान वाले नोड को चुनकर उसके पड़ोसियों पर जाना होता है।
आप कह सकते हैं कि हम साधारण रूप से डिक्शनरी की keys पर लूप चला सकते हैं:
यह तरीका काम नहीं करेगा क्योंकि यह हमें नोड्स को उनके मान के आधार पर sort करने का तरीका नहीं देता। इसलिए, साधारण arrays पर्याप्त नहीं होंगी। इस हिस्से की समस्या सुलझाने के लिए हम priority queue नाम की चीज़ का उपयोग करेंगे।
एक priority queue बिल्कुल सामान्य लिस्ट (array) जैसी होती है, लेकिन इसके प्रत्येक तत्व के साथ उनकी प्राथमिकता दर्शाने के लिए एक अतिरिक्त मान होता है। यह रही एक नमूना priority queue:
इस queue में तीन तत्व हैं — A, C, और D — और इन सबका एक प्राथमिकता मान है जो queue पर होने वाले ऑपरेशनों को निर्धारित करता है। Python priority queues के साथ काम करने के लिए बिल्ट-इन
heapqलाइब्रेरी प्रदान करता है:लाइब्रेरी में तीन फ़ंक्शन हैं जिनकी हमें परवाह है:
heapify: प्राथमिकता-मूल्य जोड़ों वाले tuples की लिस्ट को priority queue में बदल देता है।heappush: किसी तत्व को उसकी प्राथमिकता के साथ queue में जोड़ता है।heappop: सबसे अधिक प्राथमिकता वाले तत्व (सबसे छोटे मान वाले तत्व) को हटाकर लौटाता है।जैसा आप देख सकते हैं, heapify से pq को queue में बदलने के बाद, हम प्राथमिकता के आधार पर C निकालने में सक्षम हुए। आइए कोई मान push करके देखें:
queue नए तत्व की प्राथमिकता के आधार पर सही तरीके से अपडेट हो गई क्योंकि
heappopने 0 प्राथमिकता वाले नए तत्व को लौटाया।ध्यान दें कि किसी आइटम को pop करने के बाद वह queue का हिस्सा नहीं रहता।
अब, अपने एल्गोरिद्म पर वापस आते हैं,
distancesinitialize करने के बाद, हम एक नई priority queue बनाते हैं जिसमें शुरू में केवल source नोड होता है:pqके प्रत्येक तत्व की प्राथमिकता उसका वर्तमान मान होगा। हम visited नोड्स को रिकॉर्ड करने के लिए एक खाली set भी initialize करते हैं।4.
whileलूप के रूप में Dijkstra एल्गोरिद्मअब हम एक
whileलूप का उपयोग करके सभी unvisited नोड्स पर iterate करना शुरू करते हैं:जब तक priority queue खाली नहीं हो जाती, हम सबसे अधिक प्राथमिकता (न्यूनतम मान) वाले नोड को pop करते रहते हैं और उसके मान व नाम को
current_distanceऔरcurrent_nodeमें निकालते हैं। यदिcurrent_nodevisitedमें है, तो उसे छोड़ देते हैं। अन्यथा, उसे visited चिह्नित करते हैं और फिर उसके पड़ोसियों पर जाते हैं:प्रत्येक पड़ोसी के लिए, हम current नोड से tentative दूरी उसकी एज के वज़न को जोड़कर निकालते हैं। फिर जांचते हैं कि यह दूरी
distancesमें उस पड़ोसी की दूरी से छोटी है या नहीं। यदि हाँ, तो हमdistancesडिक्शनरी अपडेट करते हैं और पड़ोसी को उसकी tentative दूरी के साथ priority queue में जोड़ देते हैं।बस! हमने Dijkstra का एल्गोरिद्म इम्प्लीमेंट कर लिया। आइए इसे परखें:
तो, B से F की दूरी 9.1 है। लेकिन ठहरिए: यह पथ कौन-सा है?
5. सबसे छोटा पथ बनाना
तो, फिलहाल हमारे पास सबसे छोटी दूरियाँ हैं, पथ नहीं—जिससे हमारा ग्राफ कुछ इस तरह दिखता है:
गणना की गई सबसे छोटी दूरी से सबसे छोटा पथ बनाने के लिए, हम target से अपने कदमों को पिछड़ी दिशा में ट्रेस कर सकते हैं। F से जुड़ी प्रत्येक एज के लिए, हम उसका वज़न घटाते हैं:
फिर देखते हैं कि क्या परिणामों में से कोई F के पड़ोसियों के मान से मेल खाता है। केवल 5.6, C के मान से मेल खाता है, जिसका मतलब है कि C सबसे छोटे पथ का हिस्सा है।
हम यही प्रक्रिया C के पड़ोसी A और E के लिए दोहराते हैं:
चूँकि 2.8 E के मान से मेल खाता है, यह सबसे छोटे पथ का हिस्सा है। E, B का भी पड़ोसी है, जो B और F के बीच सबसे छोटे पथ को BECF बनाता है।
आइए इस प्रक्रिया का इम्प्लीमेंटेशन अपनी क्लास में जोड़ें। कोड ऊपर दिए गए विवरण से थोड़ा अलग है क्योंकि यह B और सभी अन्य नोड्स के बीच के सबसे छोटे पथ ढूँढता है, केवल F के नहीं।
साथ ही, यह इसे उलटी दिशा में करता है, पर मूल विचार वही है।
निम्नलिखित कोड की पंक्तियाँ
shortest_distancesमेथड के अंत में जोड़ें और पुरानाreturnस्टेटमेंट हटा दें:जब कोड चलता है, तो
predecessorsडिक्शनरी में प्रत्येक नोड का तात्कालिक parent होता है जो source तक के सबसे छोटे पथ में आता है। आइए इसे आज़माएँ:पहले, आइए
predecessorsडिक्शनरी का उपयोग करते हुए F से backtrack करके सबसे छोटा पथ manually ढूँढें:लीजिए! डिक्शनरी हमें सही बताती है कि B और F के बीच सबसे छोटा पथ BECF है।
लेकिन हमने यह तरीका आंशिक रूप से manual अपनाया। हम ऐसी मेथड चाहते हैं जो किसी भी source से किसी भी target तक
predecessorsडिक्शनरी से बना सबसे छोटा पथ स्वतः लौटा दे। हम इस मेथड कोshortest_pathके रूप में परिभाषित करते हैं (इसे क्लास के अंत में जोड़ें):shortest_distancesफ़ंक्शन का उपयोग करके हमpredecessorsडिक्शनरी बनाते हैं। फिर, हम एक while लूप शुरू करते हैं जो हर iteration में current नोड से उसके parent पर जाता है जब तक source नोड न आ जाए। इसके बाद, हम सूची को reverse करके लौटाते हैं, जिसमें source से target तक का पथ होता है।आइए इसे परखें:
यह काम करता है! आइए एक और आज़माएँ:
बिल्कुल सही।
निष्कर्ष
इस ट्यूटोरियल में, हमने ग्राफ थ्योरी के सबसे बुनियादी एल्गोरिद्म में से एक—Dijkstra’s—सीखा। यह ग्राफ-सदृश संरचनाओं में दो बिंदुओं के बीच सबसे छोटा पथ खोजने के लिए अक्सर पहला विकल्प होता है। अपनी सादगी के कारण, इसके कई उद्योगों में अनुप्रयोग हैं, जैसे:
मुझे उम्मीद है कि Python में Dijkstra’s एल्गोरिद्म का इम्प्लीमेंटेशन आपको ग्राफ एल्गोरिद्म की अद्भुत दुनिया में रुचि जगाने में सफल रहा। यदि आप और सीखना चाहते हैं, तो मैं निम्नलिखित संसाधनों की दृढ़ता से सिफारिश करता हूँ: