Hindi subtitles

← 05-15 Code for Dijkstra

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. तो यहाँ एक एल्गोरिथ्म के उस विवरण का अनुवाद पर मेरा प्रयास है
  2. में वास्तविक अजगर कोड उपयोगी संरचनाओं का उपयोग कर समाप्त हुआ
  3. शायद एक छोटे से अलग से पहले तो मैं एक Dijkstra एल्गोरिथ्म है।
  4. Dijkstra व्यक्ति जो पहले वर्णित का नाम है
  5. और इस एल्गोरिथ्म एक एकल-स्रोत लघुतम पथ के लिए विश्लेषण किया।
  6. तो हम इसे एक ही स्रोत दे। हम इसे एक एकल नोड नेटवर्क में दे।
  7. फिर हम ग्राफ जी में नेटवर्क में अन्य सभी नोड्स के लिए दूरी के लिए पूछना
  8. इतनी दूरी है अब तक एक संरचना है कि एक मानचित्रण का प्रतिनिधित्व करने के लिए जा रहा है
  9. क्या लगता है कि हम दूरी के लिए नोड्स से V से उस नोड के लिए हो सकता है।
  10. और हमारे हाथ नकली एल्गोरिथ्म में, ये गैर-लॉक हलकों में संख्याएँ हैं।
  11. कुछ नोड्स किसी भी संख्या अभी तक नहीं हो सकता है,
  12. और लोगों कि संख्या है कि मैपिंग में प्रतिनिधित्व कर रहे हैं।
  13. तो फिर हम संरचना ठीक है, कि हम V से दूर करने के लिए V पता दूरी कह द्वारा शुरू,
  14. नोड जो हम पर, शुरू कर दिया है शून्य, और हम जो हाथ के अनुकरण में रूप में अच्छी तरह से करते हैं।
  15. ठीक है, अब, वहाँ एक अतिरिक्त डेटा संरचना है, जो मैं अंतिम जिला कहते है,
  16. जो एक बार हम वास्तव में क्या है बाहर असली दूरी लगा है,
  17. हम इस संरचना में लकड़ी और ताकि मूल रूप से नंबर है कि भारी हलकों में यहाँ कर रहे हैं है।
  18. क्योंकि मैं इसे नीचे ताला लगा कर रहा हूँ जब एक सर्कल बन जाता भारी है,
  19. मैं अंतिम जिला मैपिंग में, उस नंबर चले गए और मैं यह अभी तक जिला से हटाए गए
  20. तो यह संख्या अब और अभी तक का मिलान जिला में मौजूद नहीं है।
  21. अब, हम के रूप में लंबे समय के रूप में सेट नोड्स की पुनरावृति जा रहे हैं
  22. जिसके लिए हम नोड्स की कुल संख्या से कम दूरी है परिकलित है।
  23. अब, यह थोड़ा जोखिम भरा है। मैं शायद यह किया जाता है नहीं करना चाहिए।
  24. क्योंकि अगर ग्राफ डिस्कनेक्ट कर दिया गया है, है यह है क्या यह करने के लिए जा रहा है कैसे हम मरने के लिए जा रहे हैं।
  25. ठीक है, चलो देखें जहाँ इसे है मरने के लिए जा रहा है, लेकिन यह जाएगा रखने के प्रयास नोड्स जोड़ने के लिए
  26. उनके अंतिम दूरी में भले ही वे अंतिम दूरी को जोड़ने के लिए नहीं कर रहे हैं।
  27. तो वहाँ शायद अन्य परीक्षण कि यह निर्धारित करने के लिए बेहतर हो सकता है है
  28. जब सब कुछ है कि पहुँच से बाहर है वास्तव में मान असाइन किया गया है।
  29. सामान्य में, यह परीक्षण काफी सही कसौटी नहीं है, लेकिन यह किसी कनेक्ट किए गए ग्राफ के लिए पर्याप्त होगा
  30. और है कि हम यह कोशिश जा रहे हैं।
  31. वहाँ तक है अधिक नोड्स हम का विश्लेषण करने के लिए की जरूरत है कि हम क्या करते हैं,
  32. लेने के नोड है कि सब लोगों की दूरी कम से कम अभी तक है, कहते हैं कि w, और यह नीचे बंद।
  33. यह इस मामले में नीचे बंद खिड़कियां शामिल है की जरूरत है एक डीबगिंग संदेश मुद्रित करना
  34. कह रही है कि डब्ल्यू के लिए अंतिम दूरी जो कुछ भी हम किया है के रूप में अभी तक दूर है।
  35. हम अब जानते हैं कि यह अंतिम दूरी है और तब हम जिला से अब तक कि संरचना को नष्ट।
  36. तो हम उसके पड़ोसी देशों के माध्यम से जाना।
  37. रेखांकन में w के पड़ोसियों के सभी एक एक्स कहा जाता है, और हर एक के लिए, हम कहते हैं कि हूँ,
  38. अगर हम पूरी तरह से उस पड़ोसी हल ठीक, तो हम कुछ भी नहीं है,
  39. लेकिन अगर हम तो नहीं देखते हैं अगर यह अभी तक दूर है, और अगर यह तो यह एक नहीं देता
  40. कह कर, अच्छी तरह से, दूरी हमारी सबसे अच्छा लगता है।
  41. यह कि यह w करने के लिए प्राप्त करने के लिए ले लिया दूरी से अधिक एक्स डब्ल्यू से दूरी होने जा रहा है।
  42. दूसरी ओर, यदि जाँच अगर यह पहले से ही दूरी है, नए दूरी,
  43. w के लिए दूरी से अधिक एक्स, w से दूरी दूरी से बेहतर है
  44. हम अभी तक था, और जगह अगर यह है, कि।
  45. यह कभी कभी विश्राम कहा जाता है। यह बहुत ही आराम नहीं लगता, लेकिन है कि यह क्या है।
  46. और अब तो हम उस नोड भी संभाल लिया है।
  47. इसका मतलब है कि हम नियंत्रित किया जाता है और हम w के पड़ोसियों के लिए सभी नोड्स संभाल डब्ल्यू।
  48. हम इसे नीचे बंद है, और हम आगे बढ़ने कर सकते हैं।
  49. हम वापस जाओ और अगले नोड प्रारंभ की स्थिति के लिए निकटतम संभाल।
  50. और एक बार हम सभी नोड्स के माध्यम से चला गया है और उन्हें उनके सभी अंतिम दूरी असाइन किया गया
  51. फिर हम वापस कि संरचना और हम कर रहे हैं।
  52. यह संक्षेप में Dijkstra एल्गोरिथ्म है। चलो इस का विश्लेषण।