Floyd Warshall Algorithm in Hindi | फ्लॉयड वार्शल एल्गोरिदम क्या है?


फ्लॉयड वार्शल एल्गोरिदम क्या है? (Floyd Warshall Algorithm in Hindi)

फ्लॉयड वार्शल एल्गोरिदम (Floyd Warshall Algorithm) एक डायनामिक प्रोग्रामिंग (Dynamic Programming) आधारित एल्गोरिदम है, जिसका उपयोग सभी जोड़ों (All-Pairs) के बीच सबसे छोटा मार्ग (Shortest Path) खोजने के लिए किया जाता है। यह वेटेड डायरेक्टेड ग्राफ (Weighted Directed Graph) के लिए प्रयुक्त होता है।

फ्लॉयड वार्शल एल्गोरिदम की विशेषताएँ (Characteristics of Floyd Warshall Algorithm)

  • यह सभी जोड़ों के बीच न्यूनतम दूरी (Shortest Distance Between All Pairs) खोजने के लिए प्रयुक्त होता है।
  • यह नकारात्मक वेटेड एजेस (Negative Weighted Edges) को सपोर्ट करता है, लेकिन नकारात्मक साइकल (Negative Cycle) को नहीं।
  • इसकी समय जटिलता O(V³) होती है, जहाँ V ग्राफ में वर्टिस (Vertices) की संख्या है।
  • यह एक डायनामिक प्रोग्रामिंग एल्गोरिदम है।

फ्लॉयड वार्शल एल्गोरिदम की प्रक्रिया (Process of Floyd Warshall Algorithm)

1. एक डिस्टेंस मैट्रिक्स (Distance Matrix) बनाएं, जहाँ d[i][j] = edge(i, j) हो।
2. यदि कोई एज मौजूद नहीं है, तो d[i][j] = ∞ (अनंत) सेट करें।
3. हर वर्टेक्स k के लिए:
   a. प्रत्येक वर्टेक्स i और j के लिए:
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])
4. अंतिम मैट्रिक्स में प्रत्येक जोड़ी के बीच न्यूनतम दूरी होगी।

फ्लॉयड वार्शल एल्गोरिदम का उदाहरण (Example of Floyd Warshall Algorithm)

मान लीजिए कि हमें निम्नलिखित ग्राफ दिया गया है:

स्रोत (Source) गंतव्य (Destination) वजन (Weight)
A B 3
A D 7
B A 8
B C 2
C D 1
D A 5

शुरुआती दूरी मैट्रिक्स:

A B C D
A 0 3 ∞ 7
B 8 0 2 ∞
C ∞ ∞ 0 1
D 5 ∞ ∞ 0

एल्गोरिदम लागू करने के बाद अंतिम दूरी मैट्रिक्स:

A B C D
A 0 3 5 6
B 5 0 2 3
C 6 ∞ 0 1
D 5 8 10 0

फ्लॉयड वार्शल एल्गोरिदम की समय जटिलता (Time Complexity of Floyd Warshall Algorithm)

  • समय जटिलता: O(V³) (तीन नेस्टेड लूप के कारण)
  • स्थान जटिलता: O(V²) (मैट्रिक्स स्टोरेज के कारण)

फ्लॉयड वार्शल एल्गोरिदम बनाम डिज्कस्ट्रा एल्गोरिदम (Floyd Warshall vs Dijkstra Algorithm)

विशेषता फ्लॉयड वार्शल एल्गोरिदम डिज्कस्ट्रा एल्गोरिदम
लक्ष्य सभी जोड़ों के बीच सबसे छोटा मार्ग सिंगल-सोर्स शॉर्टेस्ट पाथ
समय जटिलता O(V³) O(V log V + E)
नकारात्मक वेट सपोर्ट करता है (लेकिन नकारात्मक साइकल नहीं) सपोर्ट नहीं करता
उपयोग छोटे ग्राफ में बेहतर बड़े ग्राफ में अधिक कुशल

फ्लॉयड वार्शल एल्गोरिदम के अनुप्रयोग (Applications of Floyd Warshall Algorithm)

  • नेटवर्क रूटिंग (Network Routing)
  • नेविगेशन सिस्टम (Navigation Systems)
  • सोशल नेटवर्क विश्लेषण (Social Network Analysis)
  • बायोइन्फॉर्मेटिक्स (Bioinformatics)
  • सप्लाई चेन ऑप्टिमाइज़ेशन (Supply Chain Optimization)

निष्कर्ष

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

Related Post

Comments

Comments