मेरे पास एक ग्राफ है जिस पर मुझे अक्सर सबसे कम पथ (या बल्कि उनकी लंबाई) जानने की आवश्यकता होती है। क्योंकि मैं उन्हें पुन: गणना नहीं करना चाहता हूं, इसलिए मैं उन्हें एक साधारण सरणी में संग्रहीत करता हूं और उन्हें वहां से पुनर्प्राप्त करता हूं। हालांकि चूंकि ग्राफ समय के साथ भी बदल सकता है, इसलिए मुझे उन्हें दिए गए समय पर पुन: गणना करना होगा।गतिशील रूप से सबसे कम पथ अपडेट करना
अभी के लिए निम्न परिवर्तन हो सकता है:
एक नई धार जोड़ा जा रहा है एक बढ़त
की लंबाई को बदलने ग्राफ
करने के लिए एक नोड और इसे करने के लिए एक बढ़त जोड़ने ग्राफ
किनारे को हटाने या नोड को हटाने
सभी मामलों में सभी नोड्स हमेशा जुड़े रहेंगे और सभी किनारों के सकारात्मक वजन होंगे। ग्राफ भी अप्रत्यक्ष है। संचालन का अनुक्रम ऐसा है, कि सभी नोड हमेशा ग्राफ के एक ही घटक से होंगे। यदि इस नोड्स और किनारों को जोड़ने से पहले नोड या एज हटा दिया गया है ताकि ग्राफ कभी अलग न हो जाए।
अभी के लिए मैं केवल अद्यतन करने की योजना बना रहा हूं और फिर ग्राफ संरचना के माध्यम से सभी परिवर्तनों का प्रचार करता हूं। हालांकि मुझे यकीन नहीं है कि इसे सही ढंग से कैसे संभालें। कैश की लंबाई के इन अद्यतनों को प्राप्त करने का प्रयास कैसे करेंगे।
संपादित:
के रूप में आप में से कुछ ने बताया है कि यह सब कुछ पुनर्गणना के लिए आवश्यक हो सकता है जब एक नोड जोड़ा जाता है या एक लिंक बदल जाता है। यह उदाहरण के लिए हो सकता है जब सभी दूरी अद्यतन के माध्यम से बदल जाते हैं। हालांकि अगर मैं ग्राफ के माध्यम से परिवर्तनों का प्रचार करता हूं और डिजस्ट्रस के तरीके के समान छूट देता हूं, तो मुझे एक ही नोड को कई बार आराम करना पड़ सकता है, क्योंकि मैं इष्टतम क्रम नहीं चुन सकता। प्रश्न यह होगा कि विश्राम चरणों का आदेश कैसे दिया जाए, इसलिए मैं जितना संभव हो उतना अपडेट से बचता हूं।
यह सुनिश्चित नहीं है कि मेरे मन में वास्तविक विचार के बिना यह बहुत समझ में आता है, लेकिन मुझे उम्मीद है कि यह कुछ और स्पष्ट करेगा।
आपके पास एक रूट नोड और इससे सभी सबसे छोटे पथ हैं, या सभी नोड्स के बीच सबसे कम पथ हैं? –
नहीं, कोई रूट नोड नहीं है, बल्कि सबसे कम पथ लंबाई के सभी जोड़े हैं। – LiKao
प्रत्येक 2 बिंदुओं के लिए जो संशोधन से प्रभावित पथ से कनेक्ट किया जा सकता है, आपको सबसे कम पथ –