हमने निर्देशित ग्राफ़ (बिना वजन), जी (वी, ई), दो शीर्ष s < कोड> और t जैसे s की डिग्री और t के बाहर की डिग्री 0 के बराबर हैं। हम s से t से भिन्न-भिन्न किनारों वाले पथों को प्राप्त करना चाहते हैं एल्गोरिथ्म का उपयोग करके हम यह कर सकते हैं। बेलमैन-फोर्ड, दिज्कास्ट्रा, हफ़मैन और नेटवर्क फ्लो मुझे लगता है कि हफ़मैन इतना अप्रासंगिक है, लेकिन दूसरों के बारे में कैसे? मुझे लगता है कि नेटवर्क फ्लो का जवाब है, लेकिन मुझे पता नहीं क्यों है? Stackeeeers, कृपया मेरी मदद करो!
आप इसे नेटवर्क फ्लो के साथ कर सकते हैं यह भी:
अधिकतम किनारा-पृथक पथ
एक निर्देशित ग्राफ़ जी = (वी, ई) और दो कोने और टी के देखते हुए, हमें अधिकतम संख्या एस से टी के किनारे-पृथक मार्गों का इस समस्या को एक नेटवर्क N = (V, E) का निर्माण करके एस के साथ जी और एस के स्रोत और सी के सिंक और इकाई क्षमता के साथ प्रत्येक किनारे आवंटित करके अधिकतम प्रवाह समस्या में परिवर्तित किया जा सकता है।
इस के पीछे अंतर्ज्ञान यह है कि संवर्धन पथ खोजने के दौरान अधिकतम प्रवाह एल्गोरिदम मूल रूप से आपकी समस्या को हल करता है। एक संवर्धन पथ को सबसे अच्छा समझाया गया है:
एक संवर्धन पथ एक सरल मार्ग है - एक पथ जिसमें चक्र शामिल नहीं है - ग्राफ के माध्यम से केवल सकारात्मक क्षमता वाले किनारों का उपयोग करके सिंक के स्रोत तो ऊपर दिए बयान स्पष्ट रूप से स्पष्ट है - यदि आपको स्रोत से एक सिंक से पथ नहीं मिल सकता है जो केवल सकारात्मक क्षमता किनारों का उपयोग करता है, तो प्रवाह बढ़ नहीं सकता (जिस तरह से उस कथन का प्रमाण उतना आसान नहीं है)।
No comments:
Post a Comment