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

1. Title:
   05-15 Code for Dijkstra
2. Description:

3. 0 0:00 - 0:03
   तो यहाँ एक एल्गोरिथ्म के उस विवरण का अनुवाद पर मेरा प्रयास है
4. 3000 0:03 - 0:06
   में वास्तविक अजगर कोड उपयोगी संरचनाओं का उपयोग कर समाप्त हुआ
5. 6000 0:06 - 0:09
   शायद एक छोटे से अलग से पहले तो मैं एक Dijkstra एल्गोरिथ्म है।
6. 9000 0:09 - 0:12
   Dijkstra व्यक्ति जो पहले वर्णित का नाम है
7. 12000 0:12 - 0:16
   और इस एल्गोरिथ्म एक एकल-स्रोत लघुतम पथ के लिए विश्लेषण किया।
8. 16000 0:16 - 0:19
   तो हम इसे एक ही स्रोत दे। हम इसे एक एकल नोड नेटवर्क में दे।
9. 19000 0:19 - 0:22
   फिर हम ग्राफ जी में नेटवर्क में अन्य सभी नोड्स के लिए दूरी के लिए पूछना
10. 22000 0:22 - 0:27
    इतनी दूरी है अब तक एक संरचना है कि एक मानचित्रण का प्रतिनिधित्व करने के लिए जा रहा है
11. 27000 0:27 - 0:32
    क्या लगता है कि हम दूरी के लिए नोड्स से V से उस नोड के लिए हो सकता है।
12. 32000 0:32 - 0:37
    और हमारे हाथ नकली एल्गोरिथ्म में, ये गैर-लॉक हलकों में संख्याएँ हैं।
13. 37000 0:37 - 0:39
    कुछ नोड्स किसी भी संख्या अभी तक नहीं हो सकता है,
14. 39000 0:39 - 0:42
    और लोगों कि संख्या है कि मैपिंग में प्रतिनिधित्व कर रहे हैं।
15. 42000 0:42 - 0:48
    तो फिर हम संरचना ठीक है, कि हम V से दूर करने के लिए V पता दूरी कह द्वारा शुरू,
16. 48000 0:48 - 0:53
    नोड जो हम पर, शुरू कर दिया है शून्य, और हम जो हाथ के अनुकरण में रूप में अच्छी तरह से करते हैं।
17. 53000 0:53 - 0:56
    ठीक है, अब, वहाँ एक अतिरिक्त डेटा संरचना है, जो मैं अंतिम जिला कहते है,
18. 56000 0:56 - 0:59
    जो एक बार हम वास्तव में क्या है बाहर असली दूरी लगा है,
19. 59000 0:59 - 1:03
    हम इस संरचना में लकड़ी और ताकि मूल रूप से नंबर है कि भारी हलकों में यहाँ कर रहे हैं है।
20. 63000 1:03 - 1:06
    क्योंकि मैं इसे नीचे ताला लगा कर रहा हूँ जब एक सर्कल बन जाता भारी है,
21. 66000 1:06 - 1:11
    मैं अंतिम जिला मैपिंग में, उस नंबर चले गए और मैं यह अभी तक जिला से हटाए गए
22. 71000 1:11 - 1:15
    तो यह संख्या अब और अभी तक का मिलान जिला में मौजूद नहीं है।
23. 75000 1:15 - 1:18
    अब, हम के रूप में लंबे समय के रूप में सेट नोड्स की पुनरावृति जा रहे हैं
24. 78000 1:18 - 1:21
    जिसके लिए हम नोड्स की कुल संख्या से कम दूरी है परिकलित है।
25. 81000 1:21 - 1:23
    अब, यह थोड़ा जोखिम भरा है। मैं शायद यह किया जाता है नहीं करना चाहिए।
26. 83000 1:23 - 1:28
    क्योंकि अगर ग्राफ डिस्कनेक्ट कर दिया गया है, है यह है क्या यह करने के लिए जा रहा है कैसे हम मरने के लिए जा रहे हैं।
27. 88000 1:28 - 1:32
    ठीक है, चलो देखें जहाँ इसे है मरने के लिए जा रहा है, लेकिन यह जाएगा रखने के प्रयास नोड्स जोड़ने के लिए
28. 92000 1:32 - 1:35
    उनके अंतिम दूरी में भले ही वे अंतिम दूरी को जोड़ने के लिए नहीं कर रहे हैं।
29. 95000 1:35 - 1:38
    तो वहाँ शायद अन्य परीक्षण कि यह निर्धारित करने के लिए बेहतर हो सकता है है
30. 98000 1:38 - 1:41
    जब सब कुछ है कि पहुँच से बाहर है वास्तव में मान असाइन किया गया है।
31. 101000 1:41 - 1:46
    सामान्य में, यह परीक्षण काफी सही कसौटी नहीं है, लेकिन यह किसी कनेक्ट किए गए ग्राफ के लिए पर्याप्त होगा
32. 106000 1:46 - 1:48
    और है कि हम यह कोशिश जा रहे हैं।
33. 108000 1:48 - 1:52
    वहाँ तक है अधिक नोड्स हम का विश्लेषण करने के लिए की जरूरत है कि हम क्या करते हैं,
34. 112000 1:52 - 1:57
    लेने के नोड है कि सब लोगों की दूरी कम से कम अभी तक है, कहते हैं कि w, और यह नीचे बंद।
35. 117000 1:57 - 2:01
    यह इस मामले में नीचे बंद खिड़कियां शामिल है की जरूरत है एक डीबगिंग संदेश मुद्रित करना
36. 121000 2:01 - 2:06
    कह रही है कि डब्ल्यू के लिए अंतिम दूरी जो कुछ भी हम किया है के रूप में अभी तक दूर है।
37. 126000 2:06 - 2:12
    हम अब जानते हैं कि यह अंतिम दूरी है और तब हम जिला से अब तक कि संरचना को नष्ट।
38. 132000 2:12 - 2:14
    तो हम उसके पड़ोसी देशों के माध्यम से जाना।
39. 134000 2:14 - 2:21
    रेखांकन में w के पड़ोसियों के सभी एक एक्स कहा जाता है, और हर एक के लिए, हम कहते हैं कि हूँ,
40. 141000 2:21 - 2:26
    अगर हम पूरी तरह से उस पड़ोसी हल ठीक, तो हम कुछ भी नहीं है,
41. 146000 2:26 - 2:33
    लेकिन अगर हम तो नहीं देखते हैं अगर यह अभी तक दूर है, और अगर यह तो यह एक नहीं देता
42. 153000 2:33 - 2:35
    कह कर, अच्छी तरह से, दूरी हमारी सबसे अच्छा लगता है।
43. 155000 2:35 - 2:40
    यह कि यह w करने के लिए प्राप्त करने के लिए ले लिया दूरी से अधिक एक्स डब्ल्यू से दूरी होने जा रहा है।
44. 160000 2:40 - 2:43
    दूसरी ओर, यदि जाँच अगर यह पहले से ही दूरी है, नए दूरी,
45. 163000 2:43 - 2:46
    w के लिए दूरी से अधिक एक्स, w से दूरी दूरी से बेहतर है
46. 166000 2:46 - 2:48
    हम अभी तक था, और जगह अगर यह है, कि।
47. 168000 2:48 - 2:52
    यह कभी कभी विश्राम कहा जाता है। यह बहुत ही आराम नहीं लगता, लेकिन है कि यह क्या है।
48. 172000 2:52 - 2:54
    और अब तो हम उस नोड भी संभाल लिया है।
49. 174000 2:54 - 2:58
    इसका मतलब है कि हम नियंत्रित किया जाता है और हम w के पड़ोसियों के लिए सभी नोड्स संभाल डब्ल्यू।
50. 178000 2:58 - 3:00
    हम इसे नीचे बंद है, और हम आगे बढ़ने कर सकते हैं।
51. 180000 3:00 - 3:04
    हम वापस जाओ और अगले नोड प्रारंभ की स्थिति के लिए निकटतम संभाल।
52. 184000 3:04 - 3:07
    और एक बार हम सभी नोड्स के माध्यम से चला गया है और उन्हें उनके सभी अंतिम दूरी असाइन किया गया
53. 187000 3:07 - 3:09
    फिर हम वापस कि संरचना और हम कर रहे हैं।
54. 189000 3:09 - 3:12
    यह संक्षेप में Dijkstra एल्गोरिथ्म है। चलो इस का विश्लेषण।