एक डीएजी

Question

में नोड के माध्यम से सबसे कम पथों की संख्या की गणना करना मैं निम्नलिखित शर्तों के साथ एक डीएजी ('बीच' की अवधारणा के समान) में एक विशिष्ट नोड को पार करने वाले पथों की संख्या को गिनने के लिए एक एल्गोरिदम की तलाश में हूं। और बाधाएं:

मुझे ग्राफ़ में स्रोत/गंतव्य नोड्स के सेट के लिए गिनती करने की आवश्यकता है, न कि सभी नोड्स, यानी मध्य नोड एन के लिए, मैं जानना चाहता हूं कि नोड्स के सेट से कितने छोटे सबसे छोटे पथ एस नोड्स डी को सेट करने के लिए एन (और अलग से, मेरा मतलब है कि प्रत्येक दो पथ जिनमें कम से कम एक गैर-आम नोड है)

एएलगोरिदम आप क्या करने के लिए सुझाव दे सकते हैं, यह देखते हुए कि डीएजी हो सकता है किनारों में बहुत बड़ा लेकिन स्पैस, और मुर्गी नोड्स पर गहरी घोंसला वाली लूप को सीई वरीयता नहीं दी जाती है।

Answer 1

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