-
Title:
05-15 Code for Dijkstra
-
Description:
-
तो यहाँ एक एल्गोरिथ्म के उस विवरण का अनुवाद पर मेरा प्रयास है
-
में वास्तविक अजगर कोड उपयोगी संरचनाओं का उपयोग कर समाप्त हुआ
-
शायद एक छोटे से अलग से पहले तो मैं एक Dijkstra एल्गोरिथ्म है।
-
Dijkstra व्यक्ति जो पहले वर्णित का नाम है
-
और इस एल्गोरिथ्म एक एकल-स्रोत लघुतम पथ के लिए विश्लेषण किया।
-
तो हम इसे एक ही स्रोत दे। हम इसे एक एकल नोड नेटवर्क में दे।
-
फिर हम ग्राफ जी में नेटवर्क में अन्य सभी नोड्स के लिए दूरी के लिए पूछना
-
इतनी दूरी है अब तक एक संरचना है कि एक मानचित्रण का प्रतिनिधित्व करने के लिए जा रहा है
-
क्या लगता है कि हम दूरी के लिए नोड्स से V से उस नोड के लिए हो सकता है।
-
और हमारे हाथ नकली एल्गोरिथ्म में, ये गैर-लॉक हलकों में संख्याएँ हैं।
-
कुछ नोड्स किसी भी संख्या अभी तक नहीं हो सकता है,
-
और लोगों कि संख्या है कि मैपिंग में प्रतिनिधित्व कर रहे हैं।
-
तो फिर हम संरचना ठीक है, कि हम V से दूर करने के लिए V पता दूरी कह द्वारा शुरू,
-
नोड जो हम पर, शुरू कर दिया है शून्य, और हम जो हाथ के अनुकरण में रूप में अच्छी तरह से करते हैं।
-
ठीक है, अब, वहाँ एक अतिरिक्त डेटा संरचना है, जो मैं अंतिम जिला कहते है,
-
जो एक बार हम वास्तव में क्या है बाहर असली दूरी लगा है,
-
हम इस संरचना में लकड़ी और ताकि मूल रूप से नंबर है कि भारी हलकों में यहाँ कर रहे हैं है।
-
क्योंकि मैं इसे नीचे ताला लगा कर रहा हूँ जब एक सर्कल बन जाता भारी है,
-
मैं अंतिम जिला मैपिंग में, उस नंबर चले गए और मैं यह अभी तक जिला से हटाए गए
-
तो यह संख्या अब और अभी तक का मिलान जिला में मौजूद नहीं है।
-
अब, हम के रूप में लंबे समय के रूप में सेट नोड्स की पुनरावृति जा रहे हैं
-
जिसके लिए हम नोड्स की कुल संख्या से कम दूरी है परिकलित है।
-
अब, यह थोड़ा जोखिम भरा है। मैं शायद यह किया जाता है नहीं करना चाहिए।
-
क्योंकि अगर ग्राफ डिस्कनेक्ट कर दिया गया है, है यह है क्या यह करने के लिए जा रहा है कैसे हम मरने के लिए जा रहे हैं।
-
ठीक है, चलो देखें जहाँ इसे है मरने के लिए जा रहा है, लेकिन यह जाएगा रखने के प्रयास नोड्स जोड़ने के लिए
-
उनके अंतिम दूरी में भले ही वे अंतिम दूरी को जोड़ने के लिए नहीं कर रहे हैं।
-
तो वहाँ शायद अन्य परीक्षण कि यह निर्धारित करने के लिए बेहतर हो सकता है है
-
जब सब कुछ है कि पहुँच से बाहर है वास्तव में मान असाइन किया गया है।
-
सामान्य में, यह परीक्षण काफी सही कसौटी नहीं है, लेकिन यह किसी कनेक्ट किए गए ग्राफ के लिए पर्याप्त होगा
-
और है कि हम यह कोशिश जा रहे हैं।
-
वहाँ तक है अधिक नोड्स हम का विश्लेषण करने के लिए की जरूरत है कि हम क्या करते हैं,
-
लेने के नोड है कि सब लोगों की दूरी कम से कम अभी तक है, कहते हैं कि w, और यह नीचे बंद।
-
यह इस मामले में नीचे बंद खिड़कियां शामिल है की जरूरत है एक डीबगिंग संदेश मुद्रित करना
-
कह रही है कि डब्ल्यू के लिए अंतिम दूरी जो कुछ भी हम किया है के रूप में अभी तक दूर है।
-
हम अब जानते हैं कि यह अंतिम दूरी है और तब हम जिला से अब तक कि संरचना को नष्ट।
-
तो हम उसके पड़ोसी देशों के माध्यम से जाना।
-
रेखांकन में w के पड़ोसियों के सभी एक एक्स कहा जाता है, और हर एक के लिए, हम कहते हैं कि हूँ,
-
अगर हम पूरी तरह से उस पड़ोसी हल ठीक, तो हम कुछ भी नहीं है,
-
लेकिन अगर हम तो नहीं देखते हैं अगर यह अभी तक दूर है, और अगर यह तो यह एक नहीं देता
-
कह कर, अच्छी तरह से, दूरी हमारी सबसे अच्छा लगता है।
-
यह कि यह w करने के लिए प्राप्त करने के लिए ले लिया दूरी से अधिक एक्स डब्ल्यू से दूरी होने जा रहा है।
-
दूसरी ओर, यदि जाँच अगर यह पहले से ही दूरी है, नए दूरी,
-
w के लिए दूरी से अधिक एक्स, w से दूरी दूरी से बेहतर है
-
हम अभी तक था, और जगह अगर यह है, कि।
-
यह कभी कभी विश्राम कहा जाता है। यह बहुत ही आराम नहीं लगता, लेकिन है कि यह क्या है।
-
और अब तो हम उस नोड भी संभाल लिया है।
-
इसका मतलब है कि हम नियंत्रित किया जाता है और हम w के पड़ोसियों के लिए सभी नोड्स संभाल डब्ल्यू।
-
हम इसे नीचे बंद है, और हम आगे बढ़ने कर सकते हैं।
-
हम वापस जाओ और अगले नोड प्रारंभ की स्थिति के लिए निकटतम संभाल।
-
और एक बार हम सभी नोड्स के माध्यम से चला गया है और उन्हें उनके सभी अंतिम दूरी असाइन किया गया
-
फिर हम वापस कि संरचना और हम कर रहे हैं।
-
यह संक्षेप में Dijkstra एल्गोरिथ्म है। चलो इस का विश्लेषण।