प्रारंभ और लक्ष्य बिंदुओं के सेट के साथ ग्राफ में सबसे लंबा पथ कैसे खोजें?

Question

मेरे पास डीएजी (लागत/भार प्रति किनारे के साथ) है और नोड्स के दो सेटों के बीच सबसे लंबा रास्ता खोजना चाहता है। ग्राफ में नोड्स की कुल संख्या की तुलना में प्रारंभ और लक्ष्य नोड्स के दो सेट अलग-अलग हैं और आकार में छोटे हैं।

मुझे पता है कि एक के बीच यह कुशलतापूर्वक कैसे करें और नोड को लक्षित करें। एकाधिक के साथ, मैं प्रत्येक लक्ष्य से प्रत्येक लक्ष्य नोड तक सभी पथ सूचीबद्ध कर सकता हूं और सबसे लंबा चुन सकता हूं - लेकिन यह एकल पथ खोजों की श्रेणीबद्ध संख्या लेता है। क्या कोई बेहतर तरीका है?

Answer 1

मुझे लगता है कि आप सबसे लंबे रास्ते से संभव है कि पहले सेट से किसी भी नोड में शुरू होता है और दूसरे सेट में किसी भी नोड में समाप्त होता है।

• प्रथम नोड कोई पूर्ववर्तियों है और उसके उत्तराधिकारियों पहले सेट से नोड्स हैं: तो फिर तुम दो आभासी नोड्स जोड़ सकते हैं।

• दूसरे नोड में कोई उत्तराधिकारी नहीं है और इसके पूर्ववर्ती दूसरे सेट से नोड्स हैं।

सभी नए जोड़े गए किनारों में शून्य वजन होना चाहिए।

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

वैसे, यह समाधान अनिवार्य रूप से पहले सेट से सभी नोड्स से एल्गोरिदम निष्पादित कर रहा है, लेकिन अनुक्रमिक दृष्टिकोण के विपरीत समानांतर में आपके प्रश्न से पता चलता है।