एल्गोरिथ्म

Question

संभव डुप्लिकेट एक निर्देशित ग्राफ में अलग रास्तों की संख्या को खोजने के लिए:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

मैं एक निर्देशित ग्राफ है, क्या एल्गोरिथ्म मैं अलग की संख्या को खोजने के लिए उपयोग कर सकते हैं 2 विशेष शीर्षकों के बीच विश्वकोश पथ, और इन विशिष्ट पथों में अधिकतम पथ का उपयोग किसी भी पथ का उपयोग किया जाता है? यदि वे या तो विभिन्न प्रकार के शिखर पर जाते हैं या एक अलग क्रम में शिखर पर जाते हैं तो दो पथ अलग होते हैं।

Answer 1

यदि आप थोड़ा संशोधित डिजस्ट्रा के एल्गोरिदम का पालन करते हैं, तो आपके पास एक सब-जोड़ी समाधान हो सकता है।

स्पष्टीकरण:

1. पथ u से v को जो w
2. पथ जो w के माध्यम से जाना = रास्तों की संख्या में नहीं होता है: v को u से पथ निम्नलिखित का योग है u से wबारw से v
से पथों की संख्या

i से j (जो 1 है) से किनारे पर छोड़कर शून्य के साथ मैट्रिक्स प्रारंभ करें। तो निम्नलिखित कलन विधि आप परिणाम (सभी-जोड़ी-पथ गिनती)

for i = 1 to n: 
    for j = 1 to n: 
     for k = 1 to n: 
      paths[i][i] += paths[i][k] * paths[k][j] 

कहने की जरूरत नहीं दे देंगे: O(n^3)

एक जोड़ी समाधान को पढ़ने के लिए उत्सुक। :)