Floyd-Warshall

Question

का उपयोग करके सभी सबसे कम पथ और दूरी ढूँढना सबसे पहले, एक छोटी सी पृष्ठभूमि: मैं मूल ग्राफ एल्गोरिदम (डिज्कास्ट्रा, फ़्लॉइड-वारशॉल, बेलमैन-फोर्ड, आदि) के साथ एक साधारण ग्राफ क्लास बनाने के लिए काम कर रहा हूं। आगामी प्रोग्रामिंग प्रतियोगिता के लिए संदर्भ पत्र।

अब तक मैं फ्लोयड-Warshall की एक कार्य संस्करण है, लेकिन नकारात्मक पक्ष यह है कि अब तक यह केवल मुझे कम से कम दूरी मूल्य दोनों के बीच नोड्स, नहीं कम से कम पथ हो रही है। अधिमानतः मैं इसे पुनर्निर्माण के लिए किसी अन्य फ़ंक्शन को कॉल करने के बजाय एल्गोरिदम के भीतर पथ-निर्माण करना चाहता हूं।

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

यहाँ उदाहरण ग्राफ डेटा मैं उपयोग कर रहा हूँ है::

यहाँ मैं उपयोग कर रहा हूँ डेटा संरचनाओं पर कुछ जानकारी है

INF 10 INF INF INF INF 
INF INF 90 15 INF INF 
INF INF INF INF INF 20 
INF INF INF INF 20 INF 
INF INF 5 INF INF INF 
INF INF INF INF INF INF 

और यहाँ है वांछित मान "पथ" चर में होना चाहिए (प्रत्येक नोड्स से डिजस्ट्रा चलाकर प्राप्त):

INF 0 4 1 3 2 
INF INF 4 1 3 2 
INF INF INF INF INF 2 
INF INF 4 INF 3 2 
INF INF 4 INF INF 2 
INF INF INF INF INF INF 

यहां कोड का एक लिंक है जिसका मैं वर्तमान में एल्गोरिदम के लिए उपयोग कर रहा हूं: (via PasteBin)।

किसी भी मदद की सराहना की जाएगी!

संपादित करें: मैंने कोशिश की Wikipedia's code पथ मैट्रिक्स उत्पन्न करने के लिए और यहाँ परिणाम है:

INF INF 4 1 3 4 
INF INF 4 INF 3 4 
INF INF INF INF INF INF 
INF INF 4 INF INF 4 
INF INF INF INF INF 2 
INF INF INF INF INF INF 

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

Answer 1

हूजाह!

मैं विकिपीडिया के कोड स्निपेट जोड़ने से परिणाम में एक अच्छा कठिन ताक थी और मैं एक एडाप्टर मेरे परिणाम में एक अलग समारोह को बुलाने की आवश्यकता के बिना यह के परिणाम में परिवर्तित करने के साथ आया था:

// Time to clean up the path graph... 
for (int st_node = 0; st_node < this->size; st_node++) 
{ 
    for (int end_node = 0; end_node < this->size; end_node++) 
    { 
     int mid_node = this->path[st_node][end_node]; 

     if (mid_node == INF) 
     { 
      // There is no mid_node, it's probably just a single step. 
      if (this->graph[st_node][end_node] != INF) 
      { 
       this->path[st_node][end_node] = st_node; 
      } 

     } else { 
      // The mid_node may be part of a multi-step, find where it leads. 
      while (this->path[mid_node][end_node] != INF) 
      { 
       if (this->path[mid_node][end_node] == mid_node) { break; } // Infinite loop 
       if (this->path[mid_node][end_node] == INF) { break; } // Dead end 

       mid_node = this->path[mid_node][end_node]; 
      } 

      this->path[st_node][end_node] = mid_node; 

     } // IF mid_node 
    } // FOR end_node 
} // FOR st_node 

अनिवार्य रूप से इस नोड ए से नोड बी प्राप्त करने के लिए क्षतिपूर्ति एक मूल चरण (mid_node == INF) है जो मूल ग्राफ में मौजूद होने पर किनारे जोड़कर है। वैकल्पिक रूप से, यदि यह नोड इंगित करता है तो गंतव्य नोड (this->path[mid_node][end_node] != INF) गंतव्य के लिए केवल एक कदम पत्थर है, तब तक यह तब तक खोदता है जब तक यह पता चलता है कि यह कहां जाता है।

मदद लोगों के लिए धन्यवाद, अनुमान लगाएं कि मुझे किसी को ज़ोर से सोचने की आवश्यकता है!

Answer 2

विकिपीडिया में कुछ अच्छी जानकारी है और pseudocode है। असल में आप बस एक | वी | एक्स | वी | भरें 'अगली' मैट्रिक्स जहां तत्व I, j में वर्टेक्स की अनुक्रमणिका होती है जिसे आपको नोड i से node j तक प्राप्त करने के लिए जाना आवश्यक है। I से j का सबसे छोटा रास्ता तब से मुझे अगले [i] [j] और अगले [i] [j] से j तक पथ के रूप में दिया जा सकता है। जब तक आपके पास पूरा पथ न हो, तब तक आप पथ को इस तरह से विघटित करना जारी रखते हैं।