ग्राफ़

Question

के दो विवादित सबसेट से संबंधित किसी भी दो नोड्स के बीच सबसे छोटा रास्ता ढूंढना एक अप्रत्यक्ष ग्राफ है जिसमें प्रत्येक नोड को कुछ रंग असाइन किया जाता है। मुझे किसी भी नीले रंग के नोड से किसी भी लाल रंग के नोड में सबसे छोटा रास्ता खोजना है। (ग्राफ में अन्य रंग भी मौजूद हो सकते हैं और हालांकि इससे कोई फर्क नहीं पड़ता है लेकिन यह ज्ञात नहीं है कि वहां कितने रंग हैं।) मैं इसे बहुपद समय में कैसे कर सकता हूं?

Answer 1

एक संकेत के रूप में, ग्राफ में दो नए नोड्स जोड़ें- उन्हें एस और टी कॉल करें। लागत 0 के किनारे के साथ प्रत्येक नीले नोड को कनेक्ट करें और प्रत्येक लाल नोड को लागत 0 के किनारे के साथ टी करने के लिए कनेक्ट करें। फिर एस से टी तक सबसे छोटा रास्ता खोजें।

आशा है कि इससे मदद मिलती है!