DIZNR INTERNATIONAL

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

Ali Seron Jason

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

https://www.gyanodhan.com/video/7B1.%20GATE%20CSEIT/Algorith%20Analysis%20and%20Design/621.%20AAD%20Hindi%20-%20All%20Pair%20Shortest%20Path%20in%20hindi%20%20%20Floyd-Warshall%20Algorithm%20%20%20With%20Practical%20Example.mp4

 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] = min(dist[i][j], dist[i][k] + dist[k][j])

 यह प्रोसेस हर नोड को इंटरमीडिएट मानकर तब तक दोहराते हैं, जब तक कि हम सभी शॉर्टेस्ट पाथ न निकाल लें।

 उदाहरण (Example)

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

(A)
/ \
4 1
/ \
(B) --- 2 --- (C)

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

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)

All-Pair Shortest Path Matrix:
[0, 3, 1]
[INF, 0, 2]
[INF, INF, 0]

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)

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

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