how implement dijkstra s algorithm java
यह ट्यूटोरियल बताता है कि कैसे एक ग्राफ या ट्री में उदाहरणों की मदद से सबसे छोटे मार्गों को खोजने के लिए जावा में दिक्क्स्ट्रा के एल्गोरिथ्म को लागू करना है:
जावा में ग्राफ़ पर हमारे पहले ट्यूटोरियल में, हमने देखा कि अन्य अनुप्रयोगों के अलावा नोड्स के बीच सबसे छोटा रास्ता खोजने के लिए ग्राफ़ का उपयोग किया जाता है।
एक ग्राफ़ के दो नोड्स के बीच सबसे छोटा रास्ता खोजने के लिए, हम ज्यादातर एक एल्गोरिथ्म को नियोजित करते हैं जिसे 'के रूप में जाना जाता है' दिज्क्स्ट्रा का एल्गोरिदम ”। यह एल्गोरिथ्म ग्राफ़ या पेड़ के सबसे छोटे मार्गों को खोजने के लिए व्यापक रूप से उपयोग किया जाने वाला एल्गोरिदम बना हुआ है।
=> यहाँ सभी जावा ट्यूटोरियल की जाँच करें
आप क्या सीखेंगे:
डायजेक्स्ट्रा का एल्गोरिदम जावा में
ग्राफ में एक भारित ग्राफ और एक शुरुआत (स्रोत) शीर्ष को देखते हुए, डायजेक्स्ट्रा के एल्गोरिथ्म का उपयोग ग्राफ में स्रोत नोड से अन्य सभी नोड्स तक कम से कम दूरी खोजने के लिए किया जाता है।
ग्राफ पर डिक्स्ट्रा के एल्गोरिथ्म के चलने के परिणामस्वरूप, हम रूट के रूप में स्रोत शीर्ष के साथ सबसे छोटा पथ ट्री (SPT) प्राप्त करते हैं।
दिज्क्स्ट्रा के एल्गोरिथ्म में, हम दो सेट या सूची बनाए रखते हैं। एक में वे कोने होते हैं जो सबसे छोटे पथ के पेड़ (SPT) का हिस्सा होते हैं और दूसरे में वे कोने होते हैं जिनका मूल्यांकन SPT में शामिल किया जा रहा होता है। इसलिए हर पुनरावृत्ति के लिए, हमें दूसरी सूची से एक शीर्ष स्थान मिलता है जिसमें सबसे छोटा रास्ता है।
दिज्क्स्ट्रा के सबसे छोटे पथ एल्गोरिथ्म के लिए छद्मकोड नीचे दिया गया है।
मैं एक बिन फ़ाइल कैसे खोलूँ
स्यूडोकोड
नीचे दिए गए इस एल्गोरिथ्म के लिए छद्म कोड है।
procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end आइए अब एक नमूना ग्राफ लेते हैं और दिज्क्स्ट्रा के सबसे छोटे पथ एल्गोरिथ्म का वर्णन करते हैं ।
प्रारंभ में, एसपीटी (सबसे छोटा पथ ट्री) सेट अनंत के लिए सेट है।
आज्ञा देना शुरू करने के लिए शीर्ष के साथ 0. इसलिए शुरुआत करने के लिए हमने शीर्ष 0 को sptSet में रखा।
sptSet = {0, INF, INF, INF, INF, INF}।
स्पेटसेट में वर्टेक्स 0 के साथ, हम इसके पड़ोसियों का पता लगाएंगे। ऊर्ध्वाधर 1 और 2 क्रमशः दूरी 2 और 1 के साथ 0 के दो आसन्न नोड हैं।
उपरोक्त आंकड़े में, हमने प्रत्येक समीपवर्ती शीर्ष (1 और 2) को उनके स्रोत की दूरी 0. शीर्ष से अद्यतन किया है। अब हम देखते हैं कि शीर्ष 2 में न्यूनतम दूरी है। तो अगले हम sptSet में वर्टेक्स 2 जोड़ते हैं। इसके अलावा, हम शीर्ष 2 के पड़ोसियों का पता लगाते हैं।
अब हम न्यूनतम दूरी के साथ शिखर की तलाश करते हैं और जो कि वहाँ नहीं हैं। हम दूरी 2 के साथ शीर्ष 1 चुनते हैं।
जैसा कि हम उपरोक्त आंकड़े में देखते हैं, 2, 0, और 1 के सभी आसन्न नोड्स में से पहले से ही sptSet में हैं इसलिए हम उन्हें अनदेखा करते हैं। आसन्न नोड्स में से 5 और 3, 5 में सबसे कम लागत है। तो हम इसे स्पेससेट में जोड़ते हैं और इसके आस-पास के नोड्स का पता लगाते हैं।
उपरोक्त आकृति में, हम देखते हैं कि नोड्स 3 और 4 को छोड़कर, अन्य सभी नोड्स sptSet में हैं। 3 और 4 में से, नोड 3 में सबसे कम लागत है। तो हम इसे sptSet में डालते हैं।
जैसा कि ऊपर दिखाया गया है, अब हमारे पास केवल एक वर्टेक्स बचा है अर्थात 4 और रूट नोड से इसकी दूरी 16 है। अंत में, हमने इसे अंतिम sptSet = {0, 2, 1, 5, 3, 4} के लिए sptSet में रखा। हमें स्रोत नोड 0 से प्रत्येक शीर्ष की दूरी देता है।
जावा में डिक्स्ट्रा के एल्गोरिथ्म का कार्यान्वयन
जावा में डिक्स्ट्रा की सबसे छोटी पथ एल्गोरिथ्म का कार्यान्वयन दो तरीकों से किया जा सकता है। हम या तो प्राथमिकता कतारों और आसन्न सूची का उपयोग कर सकते हैं या हम आसन्न मैट्रिक्स और सरणियों का उपयोग कर सकते हैं।
इस खंड में, हम दोनों कार्यान्वयन देखेंगे।
एक प्राथमिकता कतार का उपयोग करना
इस कार्यान्वयन में, हम सबसे छोटी दूरी के साथ कोने को स्टोर करने के लिए प्राथमिकता कतार का उपयोग करते हैं। ग्राफ को आसन्न सूची का उपयोग करके परिभाषित किया गया है। एक नमूना कार्यक्रम नीचे दिखाया गया है।
import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i आउटपुट:
आसन्न मैट्रिक्स का उपयोग करना
इस दृष्टिकोण में, हम ग्राफ का प्रतिनिधित्व करने के लिए आसन्न मैट्रिक्स का उपयोग करते हैं। Spt सेट के लिए हम सरणियों का उपयोग करते हैं।
निम्नलिखित कार्यक्रम इस कार्यान्वयन को दर्शाता है।
import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v आउटपुट:
बार बार पूछे जाने वाले प्रश्न
Q # 1) क्या दिक्ज़स्ट्रा अप्रत्यक्ष रेखांकन के लिए काम करता है?
उत्तर: यदि रेखांकन निर्देशित या अप्रत्यक्ष है, तो दिज्क्स्ट्रा के एल्गोरिथ्म के मामले में कोई फर्क नहीं पड़ता। यह एल्गोरिदम केवल ग्राफ़ और वेट में कोने के बारे में चिंतित है।
Q # 2) दिज्क्स्ट्रा के एल्गोरिथ्म की समय जटिलता क्या है?
उत्तर: दिज्क्स्ट्रा के एल्गोरिथ्म की समय जटिलता O (V 2) है। जब न्यूनतम प्राथमिकता कतार के साथ लागू किया जाता है, तो इस एल्गोरिथ्म की समय जटिलता O (V + E l o g g V) के नीचे आ जाती है।
Q # 3) क्या दिक्जस्त्र एक लालची एल्गोरिथ्म है?
उत्तर: हां, दिज्क्स्त्र एक लालची एल्गोरिथ्म है। न्यूनतम फैले हुए वृक्ष (एमएसटी) को खोजने के लिए प्राइम के एल्गोरिथ्म के समान ये एल्गोरिदम भी एक रूट वर्टेक्स से शुरू होते हैं और हमेशा न्यूनतम पथ के साथ सबसे इष्टतम वर्टेक्स का चयन करते हैं।
Q # 4) क्या दिक्जत्र DFS या BFS है?
उत्तर: यह न तो है। लेकिन जैसा कि दिज्क्स्ट्रा का एल्गोरिथ्म इसके कार्यान्वयन के लिए प्राथमिकता कतार का उपयोग करता है, इसे बीएफएस के करीब देखा जा सकता है।
Q # 5) दिक्जस्ट्रा एल्गोरिथ्म का उपयोग कहां किया जाता है?
उत्तर: इसका उपयोग ज्यादातर रूटिंग प्रोटोकॉल में किया जाता है क्योंकि यह एक नोड से दूसरे नोड तक सबसे छोटा रास्ता खोजने में मदद करता है।
निष्कर्ष
इस ट्यूटोरियल में, हमने दिक्जस्ट्रा के एल्गोरिथ्म पर चर्चा की है। हम इस एल्गोरिथ्म का उपयोग ग्राफ या पेड़ में रूट नोड से दूसरे नोड्स तक सबसे छोटा रास्ता खोजने के लिए करते हैं।
हम आमतौर पर प्राथमिकता कतार का उपयोग करके दिक्क्स्ट्रा के एल्गोरिथ्म को लागू करते हैं क्योंकि हमें न्यूनतम पथ खोजना होगा। हम आसन्न मैट्रिक्स का उपयोग करके इस एल्गोरिथ्म को भी लागू कर सकते हैं। हमने इस ट्यूटोरियल में इन दोनों तरीकों पर चर्चा की है।
हमें उम्मीद है कि आपको यह ट्यूटोरियल उपयोगी लगेगा।
=> सभी के लिए जावा प्रशिक्षण श्रृंखला देखने के लिए यहां जाएं
अनुशंसित पाठ
- जावा में द्विआधारी खोज एल्गोरिथम - कार्यान्वयन और उदाहरण
- जावा में बबल सॉर्ट - जावा सॉर्टिंग एल्गोरिदम और कोड उदाहरण
- सम्मिलन क्रमबद्ध जावा में - सम्मिलन क्रमबद्ध एल्गोरिथ्म और उदाहरण
- चयन सॉर्ट इन जावा - चयन सॉर्ट एल्गोरिथम और उदाहरण
- क्विकॉर्ट इन जावा - एल्गोरिथम, चित्रण और कार्यान्वयन
- जावा ट्यूटोरियल फॉर बिगिनर्स: 100+ हैंड्स-ऑन जावा वीडियो ट्यूटोरियल
- उदाहरणों के साथ जावा परावर्तन ट्यूटोरियल
- जावा में दांतेदार सरणी - उदाहरणों के साथ ट्यूटोरियल
