डिजस्ट्रा के एल्गोरिदम

Question

को लागू करने के लिए मुझे पथ-खोज के एक रूप को लागू करने के लिए कार्य किया गया है (coursework @ University)। अब, स्पेस में, मैं सिर्फ एक ब्रूट फोर्स को लागू कर सकता हूं, क्योंकि खोज करने के लिए नोड्स की संख्या (प्रारंभ, दो मध्य में, अंत में) पर एक सीमा है, लेकिन मैं इस कोड का पुन: उपयोग करना चाहता हूं और Dijkstra's algorithm लागू करने के लिए आया हूं ।

मैंने विकिपीडिया पर छद्म देखा है और एक दोस्त ने मेरे लिए कुछ भी लिखा है, लेकिन यह स्पष्ट रूप से समझ में नहीं आता है। एल्गोरिदम बहुत सरल लगता है और यह समझने में मेरी कोई समस्या नहीं है, लेकिन मैं सिर्फ उस जीवन को कल्पना नहीं कर सकता जो इस तरह की चीज को महसूस करेगी।

कोई सुझाव/टिप्स?

कुछ भ्रम के लिए संपादित करें:
हां, एक लक्ष्य नोड और एक स्रोत नोड है।
मैं एक सामान्य मामले में डिजस्ट्रा को लागू करने के लिए देख रहा हूं, न कि "केवल दो मध्यवर्ती स्टॉप" मामले, क्योंकि मैं बाद में कोड का उपयोग करना चाहता हूं। अन्यथा, मैं सिर्फ एक ब्रूट-बल कार्यान्वयन लिखूंगा।
विशिष्ट समस्या जो मुझे थोड़ी परेशानी हो रही है, उप-इष्टतम अर्ध-गठित पथों को संग्रहित कर रही है, यदि वे इष्टतम हो सकते हैं। जब मैं किसी दिए गए नोड पर जा रहा हूं, तो मैं नहीं देखता कि मैं उन सभी कनेक्शनों को अपडेट करने जा रहा हूं जो इसके माध्यम से जाते हैं।
अधिक संपादित करें:
अब कुछ उत्तरों के माध्यम से जा रहे हैं और जा रहे हैं।

वास्तव में संपादित करें: मैं एक गंभीर जटिलता का उल्लेख करना भूल गया, यह है कि किसी भी दो शीर्षकों के बीच UINT_MAX अलग-अलग दूरी तक हो सकती है। माफ़ कीजिये। असल में, तथ्य यह है कि मैं इससे निपटने के लिए भूल गया था शायद पहली जगह में लापरवाही की समस्या का कारण है, हालांकि समाधान: सबसे छोटा चुनना मेरे लिए सौभाग्य से स्पष्ट है। कोई आश्चर्य नहीं कि एक दूरी चर के लिए अन्य लोगों के छद्म ने मेरी परिवर्तनीय दूरी को ध्यान में नहीं रखा।

Answer 1

यहाँ डिज्कस्ट्रा एल्गोरिथ्म के एक उच्च स्तर टूटने है:

आप एक प्राथमिकता कतार में कोने के सभी छड़ी जहां कोने के सभी स्रोत शिखर, जो के लिए को छोड़कर अनंत की प्राथमिकता (दूरी) है शून्य की दूरी (स्रोत वर्टेक्स दूरी से शून्य दूरी की शून्य इकाइयां है, है ना?)।

प्राथमिकता कतार पॉप करें। हटाए गए कशेरुक स्रोत से सबसे छोटी दूरी के साथ vertex है। स्पष्ट रूप से कतार से पॉप किया गया पहला चरम स्रोत है। अच्छी तरह से कॉल करें कि popte vertex बनाम।

v के पड़ोसियों में से प्रत्येक को देखें। उनमें से सभी की दूरी v की दूरी से अधिक होगी (अन्यथा हम उन्हें पहले से ही कतार से पॉप कर चुके होंगे, है ना?)। मान लीजिए कि वी 3 की दूरी है, और वी 3 पड़ोसियों है एक्स (जिले-से-स्रोत: 5), y (जिले-से-स्रोत: 10) और z (Dist- स्रोत से: अनंतता)।

अब हम 0 पड़ोसियों की दूरी v से देखते हैं। मान लीजिए कि वे कर रहे हैं करते हैं: - 3, y - 2, z - एक्स 4. इसका मतलब है कि एक्स लिए स्रोत है कि वी माध्यम से चला जाता से पथ की दूरी है | वी | + 3 (3 + 3 = 6), वाई की दूरी 5 (3 + 2 = 5) है और ज़ेड की दूरी 7 (3 + 4 = 7) है।

एक्स के लिए पथ के माध्यम से वी को एक्स तो हम इसे अनदेखा वर्तमान कम से कम पथ से अधिक है। हालांकि y और z के पथ जो v के माध्यम से जाने जाते हैं, पिछले ज्ञात सबसे छोटे पथ से छोटे होते हैं, इसलिए हम उन्हें अपडेट करते हैं।

आप तब तक ऐसा करते रहें जब तक कि आप सभी शीर्षकों से गुज़र चुके न हों। प्रत्येक बिंदु पर, जब आप प्राथमिकता कतार से मिनट को पॉप करते हैं तो आपको पता है कि आपको उस कशेरुक का सबसे छोटा रास्ता मिल गया है क्योंकि किसी भी संभावित छोटे पथ को v से कम दूरी के साथ एक चरम सीमा से गुज़रना होगा, जिसका अर्थ है कि हमारे पास होगा पहले से ही कतार से popped।

Answer 2

Wikipedia article link जो मैंने ओपी में भर दिया है, एनिमेटेड ग्राफिक्स के साथ एक बहुत स्पष्ट और संक्षिप्त विवरण देता है।

कुंजी जो गायब हो सकती है (?) यह है कि एल्गोरिदम के प्रत्येक चरण में आप संभवतः अपने "वर्तमान" नोड से जुड़े प्रत्येक नोड के सबसे छोटे पथ को अपडेट कर रहे हैं। आपके चार-नोड "हीरा" मामले के लिए, यदि ए प्रारंभ है और डी अंत है, तो पहले आप बी और सी तक दूरी की गणना करते हैं, फिर बी से आप ए से डी की दूरी की गणना करते हैं तो आप इसे सी के माध्यम से भी करते हैं। सी के माध्यम से पथ छोटा है, फिर "ए से डी का सबसे छोटा रास्ता" सी के माध्यम से होता है। यदि सी के माध्यम से पथ लंबा होता है, तो सबसे छोटा रास्ता बी के माध्यम से जाता है। यह स्पष्ट रूप से (?) अधिक जटिल नेटवर्क तक बढ़ाना चाहिए।

पर ओपी के सच संपादित: यह कोई फर्क नहीं पड़ता कि कितने कनेक्शन आप दो नोड्स के बीच की है। दरअसल, यह एल्गोरिदम का बिंदु है, सभी संभावित पथों के माध्यम से सभी कनेक्शनों की जांच करें। यदि नोड ए और नोड बी दो सड़कों से जुड़े हुए हैं, और आप सबसे छोटी सड़क चाहते हैं, तो लंबी सड़क के बारे में चिंता न करें, बस इसे फेंक दें। हमेशा जो डेटा आप जानते हैं उसे त्यागने का प्रयास करें आपकी समस्या के लिए प्रासंगिक नहीं है।

Answer 3

आपको जिस चीज की आवश्यकता है वह एक ग्राफ का प्रतिनिधित्व करने का एक तरीका है। आम तौर पर यह vertex ऑब्जेक्ट्स का संग्रह है, जिसमें प्रत्येक में आसन्नता सूची होती है। सी ++ में यह अन्य शीर्षकों के पॉइंटर्स की एक सूची हो सकती है। सुनिश्चित करें कि शिखर कम से कम हैं। उदाहरण के लिए, आप प्रत्येक अद्वितीय आईडी नंबर दे सकते हैं।

फिर, विकिपीडिया पर कोड को और अधिक समझना चाहिए। हर बार जब आप dist[v] की तरह छद्म कोड बनाते हैं, तो आप map<VertexIdNumber, double> का उपयोग करना चाहते हैं।

Answer 4

सी ++ में डिजस्टा के एल्गोरिदम को कार्यान्वित करना यदि आपने कभी ऐसा कुछ नहीं लिखा है तो यह एक बहुत ही गंभीर समस्या है। विकिपीडिया पेज पढ़ने के बाद, आपको शुरू करने के लिए यहां कुछ विचार दिए गए हैं।

struct Vertex { 
    int id; 
    std::vector<int> neighbors; 
    int dist_from_source; // need some sentry value for "infinity" 
    int prev; // need some sentry value for "undefined" 
}; 

यह छद्म कोड की पहली कुछ पंक्तियों पर आधारित है। एक Graphstd::vector<Vertex> हो सकता है, साथ ही दो शीर्षकों के बीच की दूरी की पहचान करने के लिए।

8  u := vertex in Q with smallest dist[] 

इस लाइन (priority_queue नहीं के रूप में हम बाद में देखेंगे) std::make_heap की आवश्यकता का संकेत। इसके लिए एक अलग वेक्टर बनाएं क्योंकि हमें इससे चीजों को जोड़ने और हटाने की आवश्यकता होगी।देखें कि एक भविष्यवाणी कैसे प्रदान करें जो हेरटेक्स को ढेर के शीर्ष पर सबसे कम dist_from_source के साथ रखती है।

12  for each neighbor v of u: // where v has not yet been removed from Q. 

यहाँ कारण है कि हम Q के लिए priority_queue का उपयोग नहीं करते है। आपको यह पता लगाना होगा कि v अभी भी Q में है या नहीं। प्राथमिकता_क्यू आपको ऐसा करने नहीं देती है।

13  alt := dist[u] + dist_between(u, v) 

अब आपको Graph के साथ आने वाले दूरी समारोह की आवश्यकता है। आपने यह नहीं कहा कि ग्राफ़ डेटा कैसे परिभाषित किया गया है, इसलिए आप यहां पर थोड़े हैं।

17  return dist[] 

यह लाइन केवल सबसे कम पथ बनाने के लिए आवश्यक डेटा लौटने का मतलब है। यह मूल रूप से उन सभी को होने prev और dist_from_source में भर साथ vertexes का सेट है।

Answer 5

विशिष्ट मुद्दा यह है कि मैं के साथ उप इष्टतम आधे का गठन पथ भंडारण है एक छोटे से समस्या हो रही है, मामले में वे हो सकता है इष्टतम बनें। जब मैं किसी दिए गए नोड पर जा रहा हूं, तो मैं नहीं देखता कि मैं उन सभी कनेक्शनों को अपडेट करने जा रहा हूं जो इसके माध्यम से जाते हैं।

मुझे लगता है कि शायद आप एल्गोरिदम को थोड़ा गलत समझ रहे हैं। डिजस्ट्रा दूरी के बढ़ते क्रम में नोड्स की खोज करके काम करता है; इसलिए आपको स्थायी रूप से लेबल किए गए किसी भी नोड के लिए न्यूनतम दूरी और इष्टतम पथ प्राप्त करने की गारंटी है।

एल्गोरिदम चलाने पर आप सामान्य रूप से किसी भी पथ को स्पष्ट रूप से स्टोर नहीं करेंगे। इसके बजाय, मान लें कि आप ग्राफ पर एक फैला हुआ पेड़ बना रहे हैं - इसलिए उस पेड़ पर प्रत्येक नोड को पाने का केवल एक ही तरीका है। आपको प्रत्येक नोड के खिलाफ स्टोर करने की आवश्यकता है एक दूरी लेबल और उसके माता-पिता। जब आप पहली बार खोज के दौरान प्रत्येक नोड देखते हैं, तो आप इसे लेबल रूप से लेबल करेंगे; यह संभव है कि बाद में आपको इसके लिए एक बेहतर मार्ग मिलेगा - लेकिन उस बिंदु पर आपको अपडेट करना होगा, उस एकल नोड के लिए दूरी और पैरेंट लेबल हैं।

एक बार जब आप स्थायी रूप से अपना गंतव्य लेबल करते हैं, तो आप रुक सकते हैं, और फिर आप पैरेंट लेबल को स्रोत पर वापस चलाकर इसे इष्टतम मार्ग प्राप्त कर सकते हैं।

आशा में मदद करता है :)

Answer 6

यह प्रतिक्रिया आप के लिए बहुत देर हो चुकी हो सकता है, लेकिन मैं मामले में यह पेशकश करते हैं दूसरों के लिए मदद की है।

सबसे पहले आप, स्पष्ट करने के लिए है कि क्या

1. नोड्स के बीच किनारों अलग वजन
2. ग्राफ निर्देश दिया जाता है या अनिर्दिष्ट

के बाद से मैं विश्वविद्यालय में ऐसे एल्गोरिथम का अध्ययन यह 25 साल हो गया है है की जरूरत है लेकिन स्मृति से वॉरशेल एल्गोरिदम मैट्रिक्स विधि द्वारा कार्यान्वित करना आसान है। आप यहां देख सकते हैं: www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf]।