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

Question

में कम से कम पथ को बचाने के लिए

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

Answer 1

की सूची संग्रहीत आप विकिपीडिया लिंक आपके द्वारा दिया गया से pseudocode को देखें, तो तुम वहाँ में एक शृंखला देखेंगे prev[] बुलाया दे। इस सरणी प्रत्येक नोड वी ग्राफ में के लिए, शामिल है, पिछले नोड यू स्रोत नोड रों और वी बीच कम से कम पथ में। रों और वी बीच कम से कम पथ (। इस सरणी भी पूर्ववर्ती या माता पिता सरणी कहा जाता है)

दूसरे शब्दों में, यह है:

s -> u -> v 
where u = prev[v] 

रों से पथ से u में कई नोड्स हो सकते हैं, ताकि से से v पर पथ का पुनर्निर्माण किया जा सके।, तो आप सिर्फ पथ मुख्य स्यूडोकोड नीचे कोड स्निपेट का उपयोग कर prev[] सरणी द्वारा परिभाषित किया गया साथ वापस चलना (लक्ष्यवी है): ऐसा करने के लिए

1 S ← empty sequence 
2 u ← target 
3 while prev[u] is defined:     // Construct the shortest path with a stack S 
4  insert u at the beginning of S   // Push the vertex onto the stack 
5  u ← prev[u]        // Traverse from target to source 
6 end while 

Answer 2

इस पुस्तकालय का उपयोग करने वाले अधिकांश पुस्तकालयों से आपको ऐसा करने का एक तरीका मिल जाएगा। लेकिन सामान्य रूप से बस प्रत्येक नोड के पथ का ट्रैक रखें। यानी प्रत्येक नोड एक attrribute shortestPathToNode जिसमें आप नोड्स

Answer 3

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

// Function to print shortest path from source to j using parent array 
void path(parent array, int j) 
{ 
    // Base Case : If j is source 
    if (jth element of parent is -1) return; 
  
    path(parent, jth element of parent); 
  print j; 
} 

ध्यान दें कि मुद्रण "j" के बजाय बाहर, आप इसे एक वैश्विक वेक्टर में स्टोर कर सकते हैं: यहाँ प्रत्यावर्तन टुकड़ा को समझने के लिए एक बहुत ही कम और आसान है बाद में उपयोग के लिए।