Hindi subtitles

← 05-22 All Pairs Shortest Paths

Get Embed Code
3 Languages

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

  1. जैसा कि हम पिछले इकाई एक सामाजिक नेटवर्क में सबसे अधिक केंद्रीय नोड को खोजने के लिए, में चर्चा की,
  2. यह एक ग्राफ में प्रत्येक नोड लेते हैं और कितनी दूर यह है पता लगाने के लिए सक्षम होना करने के लिए उपयोगी है
  3. एक वर्ग के लिए एक विशेष नोड करने के लिए ग्राफ में सभी अन्य नोड्स से और फिर दोहराने के लिए
  4. उस ऑपरेशन अनिवार्य रूप से हर दूसरे नोड हर दूसरे नोड से दूरी पता करने के लिए।
  5. वास्तव में क्या हम पता करने के लिए चाहते हैं किसी भी जोड़ी नोड्स के बीच दूरी कम से कम है।
  6. तो सभी जोड़े हम की दूरी - कम से कम पथ की लंबाई पता करने के लिए चाहते हैं।
  7. अब, कि हम किसी भी दिए गए नोड, फिर एम से एक सबसे छोटा रास्ता निष्पादित कर सकते हैं दी * logn समय।
  8. हम बस से एल्गोरिथ्म, दोहरा सकते हैं सिर्फ एक-एक कर प्रत्येक नोड के लिए चलाएँ Dijkstra-
  9. यहाँ एक नोड है Dijkstra - यहाँ चलाने के एक नोड Dijkstra - चला तो आप सभी नोड्स के लिए इसे दोहराएँ।
  10. तो हम एन मिल सकें की संख्या कुल समय के लिए nlogn टाइम्स
  11. सभी जोड़े नोड्स के बीच की दूरी पाने के लिए।
  12. इस मात्रा कैसे घने से कनेक्ट ग्राफ़ करें है के आधार पर मानों की एक श्रेणी है सकते हैं।
  13. अगर ग्राफ कनेक्ट किए गए, लेकिन बहुत ही विरल है, तो हम n²logn एम एन - के रूप में ही है।
  14. ग्राफ बहुत घनी कनेक्ट है, तो फिर किनारों की संख्या लगभग वर्ग है
  15. वर्टेक्स और ऐसा की संख्या के चल रहे समय, कम से कम शब्दों में
  16. वर्टेक्स की संख्या के, अब nÂłlog n बन जाता है।
  17. आप फिबोनैकी ढेर विचार का उपयोग अब, थोड़ा सा यह की तुलना में बेहतर कर सकते हैं
  18. सबसे अच्छा है कि आप कर सकते हैं कि मैं पहले उल्लेख किया गया, लेकिन यह हो सकता है
  19. व्यावहारिक रूप से ऐसी संहिता के संदर्भ में।
  20. अब इस पर दूसरी ओर हम यह हरा सकते हैं।