AAD Hindi – All Pair Shortest Path in hindi Floyd-Warshall Algorithm With Practical Example
Contents
- 1 Floyd-Warshall Algorithm का परिचय
- 1.1 एल्गोरिदम की मुख्य अवधारणा
- 1.2 उदाहरण (Example)
- 1.3 मान लीजिए हमारे पास यह ग्राफ है:
- 1.4 वेटेड एड्ज मैट्रिक्स:
- 1.5 Python कोड (Floyd-Warshall Algorithm)
- 1.6 आउटपुट (Final Shortest Path Matrix)
- 1.7 टाइम और स्पेस कॉम्प्लेक्सिटी
- 1.8 Floyd-Warshall Algorithm के उपयोग (Applications)
- 1.9 निष्कर्ष (Conclusion)
- 1.10 क्या आप Bellman-Ford Algorithm या Dijkstra Algorithm भी समझना चाहेंगे?
- 1.11 AAD Hindi – All Pair Shortest Path in hindi Floyd-Warshall Algorithm With Practical Example
All Pair Shortest Path (Floyd-Warshall Algorithm) – Explained in Hindi with Example
Floyd-Warshall Algorithm एक डायनेमिक प्रोग्रामिंग आधारित एल्गोरिदम है जो सभी जोड़ी (All Pair) शॉर्टेस्ट पाथ निकालने के लिए प्रयोग किया जाता है। यह एल्गोरिदम ग्राफ में सभी नोड्स के बीच सबसे छोटा रास्ता खोजने में मदद करता है।
Floyd-Warshall Algorithm का परिचय
यह डायरेक्टेड (Directed) वेटेड ग्राफ पर काम करता है।
यह नेगेटिव वेट एज (Negative Weight Edge) को भी हैंडल कर सकता है (लेकिन नेगेटिव साइकिल को नहीं)।
इसका टाइम कॉम्प्लेक्सिटी O(N³) होती है, जहाँ N = नोड्स की संख्या।
एल्गोरिदम की मुख्य अवधारणा
मान लीजिए कि हमारे पास N नोड्स का एक ग्राफ है।
एक डिस्टेंस मैट्रिक्स (Distance Matrix) बनाते हैं, जहाँ
- dist[i][j] = i से j तक जाने की सबसे छोटी दूरी
- अगर कोई डायरेक्ट एज नहीं है, तो Infinity (INF) लेते हैं
अब हम हर नोड k को इंटरमीडिएट नोड मानकर सभी नोड्स के बीच के रास्ते अपडेट करते हैं:
यह प्रोसेस हर नोड को इंटरमीडिएट मानकर तब तक दोहराते हैं, जब तक कि हम सभी शॉर्टेस्ट पाथ न निकाल लें।
उदाहरण (Example)
मान लीजिए हमारे पास यह ग्राफ है:
वेटेड एड्ज मैट्रिक्स:
A | B | C | |
---|---|---|---|
A | 0 | 4 | 1 |
B | ∞ | 0 | 2 |
C | ∞ | ∞ | 0 |
Python कोड (Floyd-Warshall Algorithm)
आउटपुट (Final Shortest Path Matrix)
Explanation:A → B
का शॉर्टेस्ट पाथ: 3 (A → C → B)A → C
का शॉर्टेस्ट पाथ: 1B → C
का शॉर्टेस्ट पाथ: 2B → A
और C → A, C → B
के लिए कोई रास्ता नहीं (INF)
टाइम और स्पेस कॉम्प्लेक्सिटी
Time Complexity: O(N³)
Space Complexity: O(N²)
(Distance Matrix)
Floyd-Warshall Algorithm के उपयोग (Applications)
नेटवर्क रूटिंग (Network Routing)
मैप्स और नेविगेशन सिस्टम (Google Maps, GPS)
सोशल नेटवर्क एनालिसिस
डेटा सेंटर और पैकेट स्विचिंग
निष्कर्ष (Conclusion)
- Floyd-Warshall Algorithm सभी नोड्स के बीच सबसे छोटा रास्ता निकालने के लिए बहुत उपयोगी है।
- यह डायनेमिक प्रोग्रामिंग का उपयोग करता है और O(N³) समय में चलता है।
- नेगेटिव वेट को हैंडल कर सकता है, लेकिन नेगेटिव साइकिल को नहीं।