DIZNR INTERNATIONAL

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

Ali Seron Jason 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

Here’s a complete explanation of the Floyd-Warshall Algorithm (All Pair Shortest Path) in Hindi with a practical example, perfect for B.Tech, BCA, GATE, or competitive exams under AAD (Advanced Algorithm Design).

Floyd-Warshall Algorithm (All-Pairs Shortest Path) – हिंदी में

क्या है Floyd-Warshall Algorithm?

Floyd-Warshall एक Dynamic Programming आधारित एल्गोरिथ्म है जिसका उपयोग एक ग्राफ के सभी नोड्स के बीच की सबसे छोटी दूरी (All-Pairs Shortest Path) खोजने के लिए किया जाता है।

Algorithm का उद्देश्य:

एल्गोरिदम की स्टेप्स (हिंदी में)

मान लीजिए हमारे पास n nodes वाला एक ग्राफ है। हम एक Distance Matrix (D) बनाएंगे, जहाँ:

अब हम तीन nested loops चलाते हैं:

for k = 1 to n:
   for i = 1 to n:
      for j = 1 to n:
         if D[i][j] > D[i][k] + D[k][j]:
             D[i][j] = D[i][k] + D[k][j]

यह चेक करता है कि क्या i से j की current distance से बेहतर रास्ता k के through हो सकता है।

Practical Example:

मान लीजिए हमारे पास 4 vertex हैं और नीचे दिया गया weighted graph है:

Graph Matrix (Adjacency):
      0   3   ∞   7
      8   0   2   ∞
      5   ∞   0   1
      2   ∞   ∞   0

इसे हम Distance Matrix D मानते हैं। अब हम Floyd-Warshall एल्गोरिद्म लगाते हैं।

Update होता रहेगा जैसे:

अंतिम Matrix सभी node pairs के बीच की minimum distances को दर्शाती है।

Final Output (Shortest Distance Matrix):

(After applying Floyd-Warshall)

    0   3   5   6
    7   0   2   3
    5   8   0   1
    2   5   7   0

Time Complexity:

O(n3)O(n^3)

Key Points:

विशेषता विवरण
Input Weighted graph (matrix)
Allowed Weights Positive or Negative
Not Allowed Negative Cycles
Complexity O(n3)O(n^3)
Technique Dynamic Programming

Need Extra Help?

Would you like:

Just tell me and I’ll provide the exact format you need!