डिजस्ट्रा के एल्गोरिदम के कार्यान्वयन में मेरे पास सभी नोड्स और 1 प्राथमिकता कतार सभी नोड्स के साथ 1 सरणी है। जब भी कोई नोड निकलता है तो मैं नई दूरी के साथ सभी आसन्न नोड्स को अपडेट करता हूं और यह कहां से आया, इसलिए मैं पथ को पीछे हट सकता हूं।प्राथमिकता कतार
प्राथमिकता कतार में नोड नई दूरी के साथ अद्यतन किया गया है और सरणी में नोड अद्यतन किया गया है जहां से यह नई दूरी से आया था। जब एक नोड dequeued है सरणी में अंतिम दूरी अद्यतन किया जाता है:
PathInfo current = pq.remove();
path[current.pos].distance = current.distance;
यह दोनों पिछले नोड और दूरी के साथ प्राथमिकता कतार के बारे में जानकारी के साथ सरणी अद्यतन करने के लिए स्वीकार्य है?
यह तब होता है जब भी एक बेहतर दूरी पाया जाता है:
PathInfo key(i, newDistance);
path[i].distance = newDistance;
path[i].previous = current.pos;
pq.decreaseKey(key);
यह थोड़ा निरर्थक मूलतः एक ही जानकारी के साथ अपने सरणी और प्राथमिकता कतार अद्यतन करने के लिए लगता है।
मैं वर्तमान में पीक्यू में डेटा संरचना के रूप में एक नियमित सरणी का उपयोग कर रहा हूं। प्राथमिकता को अद्यतन करना रैखिक समय में किया जाता है और रैखिक समय में डेक्यूइंग भी किया जाता है।
प्राथमिकता कतार में मुझे किस डेटा संरचना का उपयोग करना चाहिए और मुझे नोड्स प्राथमिकता को कैसे बदलना चाहिए?
मैं सी ++
मुझे सरणी में दूरी को अद्यतन करना है। अगर मैं अपने पीक्यू से नोड आसन्न नोड्स को बेहतर दूरी दे सकता हूं तो मुझे और कैसे तुलना करना चाहिए? – Carlj901
आदर्श रूप से, आप इसे अपने पीक्यू से देखने में सक्षम होना चाहिए। यदि यह ऑपरेशन अनुपलब्ध है (और आपके पीक्यू कार्यान्वयन में जोड़ा नहीं जा सकता है), तो आपको अनावश्यक जानकारी को बनाए रखने की आवश्यकता होगी। [मैं अपने उत्तर में इस पर एक सेक्शन जोड़ूंगा] – comingstorm
सबसे बेहतर होगा अगर मैं अपने पीक्यू में एक ढेर बनाए रख सकूं और एक हैश फ़ंक्शन हो जो प्रत्येक नोड्स नाम (2 डी सरणी में स्थिति) को इसकी दूरी पर मैप करें। यकीन नहीं है कि मैं इसे कैसे लागू करूंगा। – Carlj901