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