AAD Hindi – All Pair Shortest Path in hindi Floyd-Warshall Algorithm With Practical Example

March 11, 2025March 12, 2025 Ali Seron Jason 0 Comments

00:00

Contents [hide]

0.1 All Pair Shortest Path (Floyd-Warshall Algorithm) – Explained in Hindi with Example

1 Floyd-Warshall Algorithm का परिचय

All Pair Shortest Path (Floyd-Warshall Algorithm) – Explained in Hindi with Example

Floyd-Warshall Algorithm एक डायनेमिक प्रोग्रामिंग आधारित एल्गोरिदम है जो सभी जोड़ी (All Pair) शॉर्टेस्ट पाथ निकालने के लिए प्रयोग किया जाता है। यह एल्गोरिदम ग्राफ में सभी नोड्स के बीच सबसे छोटा रास्ता खोजने में मदद करता है।

Available For 100% Free Book/Notes PDF Download (Click Here)

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)

import sys



 

# Define number of vertices

N = 3  
# Infinity value (for no direct path)

INF = sys.maxsize



 

# Graph adjacency matrix (distance representation)

dist = [

    [0, 4, 1],

    [INF, 0, 2],

    [INF, INF, 0]

]
# Floyd-Warshall Algorithm

def floyd_warshall():

    global dist

    for k in range(N):  # Intermediate node

        for i in range(N):  # Source node

            for j in range(N):  # Destination node

                if dist[i][k] != INF and dist[k][j] != INF:

                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])



 

# Run algorithm

floyd_warshall()

# Print final shortest path matrix print("All-Pair Shortest Path Matrix:") for row in dist: print(row)

आउटपुट (Final Shortest Path Matrix)

Explanation:
A → B का शॉर्टेस्ट पाथ: 3 (A → C → B)
A → C का शॉर्टेस्ट पाथ: 1
B → C का शॉर्टेस्ट पाथ: 2
B → 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³) समय में चलता है।
नेगेटिव वेट को हैंडल कर सकता है, लेकिन नेगेटिव साइकिल को नहीं।

DIZNR INTERNATIONAL

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 का परिचय

एल्गोरिदम की मुख्य अवधारणा

उदाहरण (Example)

मान लीजिए हमारे पास यह ग्राफ है:

वेटेड एड्ज मैट्रिक्स:

Python कोड (Floyd-Warshall Algorithm)

आउटपुट (Final Shortest Path Matrix)

टाइम और स्पेस कॉम्प्लेक्सिटी

Floyd-Warshall Algorithm के उपयोग (Applications)

निष्कर्ष (Conclusion)

क्या आप Bellman-Ford Algorithm या Dijkstra Algorithm भी समझना चाहेंगे?