फ़्लॉइड-वॉर्शल एल्गोरिथम: कोडिंग साक्षात्कार गाइड

टीएल;डीआर: फ्लोयड-वॉर्शल एल्गोरिदम गतिशील प्रोग्रामिंग के साथ सभी जोड़े के सबसे छोटे पथों की गणना करता है। ग्राफ़ से दूरी मैट्रिक्स आरंभ करें, फिर प्रत्येक मध्यवर्ती शीर्ष k के लिए प्रत्येक जोड़ी को dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) के साथ अपडेट करें। यह O(V³) समय और O(V²) स्थान में चलता है और नकारात्मक विकर्ण प्रविष्टियों के माध्यम से नकारात्मक चक्रों को उजागर कर सकता है।

फ़्लॉइड-वॉर्शल एल्गोरिथम क्या है?

फ्लोयड-वॉर्शॉल प्रत्येक क्रमित शीर्षों के जोड़े के बीच सबसे छोटे पथ के लिए एक गतिशील प्रोग्रामिंग एल्गोरिदम है। यह निर्देशित या अप्रत्यक्ष भारित ग्राफ़ के साथ काम करता है और नकारात्मक किनारों की अनुमति देता है। हालाँकि, यदि कोई प्रासंगिक नकारात्मक-भार चक्र मौजूद है, तो कुछ सबसे छोटे रास्तों का कोई सीमित न्यूनतम नहीं होता है क्योंकि चक्र को बार-बार पार करने से पथ की लागत कम होती रहती है।

एल्गोरिथ्म यादगार है क्योंकि यह एक वैश्विक पथ समस्या को एक निर्णय में बदल देता है: वर्तमान मध्यवर्ती शीर्ष k के लिए, क्या i से j तक का सबसे अच्छा ज्ञात पथ बेहतर है, या i से k और फिर k से j तक जाने से?

आप पुनरावृत्ति कैसे प्राप्त करते हैं?

D(k, i, j) को i से j तक की सबसे छोटी दूरी के रूप में परिभाषित करें जिसके मध्यवर्ती शीर्ष केवल पहले k शीर्षों से आ सकते हैं। सबसे छोटा अनुमत पथ या तो D(k−1, i, j) को ध्यान में रखते हुए शीर्ष k से बचता है, या k का उपयोग करता है और i से k तक सर्वोत्तम अनुमत पथ और k से j तक सर्वोत्तम अनुमत पथ में विभाजित हो जाता है।

वह पुनरावृत्ति देता है:

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

क्योंकि चरण k केवल चरण k−1 मानों पर संगत तरीके से निर्भर करता है, मैट्रिक्स को उसी स्थान पर अद्यतन किया जा सकता है। यह तर्क महत्वपूर्ण लूप क्रम की भी व्याख्या करता है: k सबसे बाहरी लूप होना चाहिए। I या j को बाहर रखने से अपरिवर्तनीय परिवर्तन हो जाता है और आंशिक रूप से अनुमत पथों का गलत उपयोग हो सकता है।

आप दूरी मैट्रिक्स को कैसे प्रारंभ करते हैं?

V बटा V मैट्रिक्स बनाएं। dist[i][i] को शून्य पर सेट करें, सीधे किनारे की सेल को उसके वजन पर सेट करें, और जब कोई सीधा किनारा मौजूद न हो तो अनंत का उपयोग करें। यदि समानांतर किनारे संभव हैं, तो सबसे छोटा सीधा भार रखें। दो दूरियाँ जोड़ने से पहले, सत्यापित करें कि दोनों परिमित हैं ताकि अनंत प्रहरी अतिप्रवाह न कर दे या गलत उम्मीदवार न बना दे।

आप एक साक्षात्कार में फ़्लॉइड-वॉर्शल का पता कैसे लगाते हैं?

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

आम तौर पर आपको बड़े उदाहरण के लिए प्रत्येक मैट्रिक्स को खींचने की आवश्यकता नहीं होती है। एक सुधार और एक अपरिवर्तित मान सहित, अपरिवर्तनीय को प्रदर्शित करने के लिए पर्याप्त कोशिकाओं का पता लगाएं। बताएं कि k को पूरा करने के बाद, प्रत्येक मैट्रिक्स प्रविष्टि उन पथों के बीच इष्टतम है जिनके मध्यवर्ती कोने संसाधित सेट तक सीमित हैं।

आपको कौन सा छद्मकोड लिखना चाहिए?

बाहर की ओर k के साथ तीन नेस्टेड लूप का उपयोग करें:

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

परिमित जाँच और संख्यात्मक प्रकार को समझाइये। बड़े पूर्णांक प्रहरी वाली भाषाओं में, नकारात्मक मान में अनंत जोड़ने से परिमित या अतिप्रवाह दिख सकता है। एक गार्ड शुद्धता का हिस्सा है, न कि केवल एक कार्यान्वयन विवरण।

समय और स्थान की जटिलताएँ क्या हैं?

तीन लूप k, i, और j के प्रत्येक संयोजन की जांच करते हैं, इसलिए रनटाइम O(V³) है। दूरी मैट्रिक्स O(V²) स्थान घेरता है। इन-प्लेस अपडेट करने से त्रि-आयामी तालिका से बचा जाता है, जबकि पथ पुनर्निर्माण के लिए नेक्स्ट-हॉप या पूर्ववर्ती मैट्रिक्स O(V²) अधिक स्थान जोड़ता है।

फ़्लॉइड-वॉर्शल अक्सर मामूली घने ग्राफ़ के लिए आकर्षक होता है क्योंकि इसका कार्यान्वयन कॉम्पैक्ट और पूर्वानुमानित होता है। गैर-नकारात्मक किनारों वाले बड़े विरल ग्राफ़ के लिए, प्रत्येक स्रोत से डिज्क्स्ट्रा चलाना अधिक कुशल हो सकता है। चुनने से पहले हमेशा आवश्यक आउटपुट, ग्राफ घनत्व, वजन की कमी और शीर्ष गणना की तुलना करें।

आप वास्तविक सबसे छोटे पथ का पुनर्निर्माण कैसे करते हैं?

केवल दूरियाँ ही शीर्ष अनुक्रम को प्रकट नहीं करतीं। जब i से j तक कोई सीधा किनारा मौजूद हो, तो j से प्रारंभ किए गए next[i][j] मैट्रिक्स को बनाए रखें। जब भी k के माध्यम से रूटिंग से dist[i][j] में सुधार होता है, तो next[i][j] को next[i][k] पर सेट करें। किसी पथ का पुनर्निर्माण करने के लिए, गंतव्य तक पहुँचने तक बार-बार वर्तमान शीर्ष से next[current][destination] तक जाएँ।

पुनर्निर्माण से पहले पहुंच योग्य न होने वाली जोड़ियों की जांच करें, और नकारात्मक-चक्र के मामलों से बचाव करें। यदि कोई जोड़ा नकारात्मक चक्र की यात्रा कर सकता है और फिर गंतव्य तक पहुंच सकता है, तो पुनर्निर्माण के लिए कोई सीमित छोटा रास्ता नहीं है।

फ़्लॉइड-वॉर्शल नकारात्मक चक्रों का पता कैसे लगाता है?

एल्गोरिदम समाप्त होने के बाद, विकर्ण का निरीक्षण करें। एक मान dist[v][v] < 0 साबित करता है कि एक नकारात्मक-भार चक्र v से पहुंच योग्य है और v पर वापस आ सकता है। यह केवल एक नकारात्मक बढ़त खोजने से अधिक मजबूत है; नकारात्मक किनारे पूरी तरह से मान्य सबसे छोटे पथ वाले ग्राफ़ में मौजूद हो सकते हैं।

यदि साक्षात्कारकर्ता पूछता है कि कौन से जोड़े प्रभावित हैं, तो प्रत्येक i और j की पहचान करें जिसके लिए i ऐसे शीर्ष तक पहुँच सकता है v और v j तक पहुँच सकता है। वे जोड़े नकारात्मक चक्र के माध्यम से मनमाने ढंग से कई बार लूप कर सकते हैं, इसलिए उनका सबसे छोटा-पथ मान सीमित नहीं है।

आपको दूसरा सबसे छोटा पथ एल्गोरिदम कब चुनना चाहिए?

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

आपको किन साक्षात्कार गलतियों से बचना चाहिए?

किसी अन्य लूप के अंदर k न डालें, विकर्ण पर शून्य को न भूलें, गार्ड के बिना अनंत जोड़ें, नकारात्मक चक्रों के साथ नकारात्मक किनारों को भ्रमित करें, या दावा करें कि O(V²) मैट्रिक्स स्पेस में प्रत्येक प्रतिनिधित्व में स्वचालित रूप से इनपुट शामिल होता है। स्पष्ट करें कि क्या ग्राफ निर्देशित है, क्या समानांतर किनारे मौजूद हैं, और क्या साक्षात्कारकर्ता को दूरी, पथ या चक्र-प्रभावित जोड़े की आवश्यकता है।

कोडिंग साक्षात्कार सहायक वर्कफ़्लो का अभ्यास करें, बेलमैन-फोर्ड एल्गोरिदम की तुलना करें, और बिग ओ जटिलता चीट शीट की समीक्षा करें।

अक्सर पूछे जाने वाले प्रश्न

केवल लूप्स का ही नहीं, अपरिवर्तनीय का भी अभ्यास करें

YesToTheOffer एक कोडिंग स्पष्टीकरण तैयार करने, इसे आपके निजी तैयारी नोट्स में शामिल करने, किनारे के मामलों की जांच करने और बाद की समीक्षा के लिए साक्षात्कार प्रतिलेख को संरक्षित करने में मदद कर सकता है।