Algorithm Analysis and Design 

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

Ali Seron Jason 0 Comments

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

play-rounded-fill play-rounded-outline play-sharp-fill play-sharp-outline
pause-sharp-outline pause-sharp-fill pause-rounded-outline pause-rounded-fill
00:00
© 2018 Flowplayer ABAbout FlowplayerGPL based license

 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 को इंटरमीडिएट नोड मानकर सभी नोड्स के बीच के रास्ते अपडेट करते हैं:
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)

  • Floyd-Warshall Algorithm सभी नोड्स के बीच सबसे छोटा रास्ता निकालने के लिए बहुत उपयोगी है।
  • यह डायनेमिक प्रोग्रामिंग का उपयोग करता है और O(N³) समय में चलता है।
  • नेगेटिव वेट को हैंडल कर सकता है, लेकिन नेगेटिव साइकिल को नहीं।

 क्या आप 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 का उद्देश्य:

  • Directed या Undirected ग्राफ में
  • Negative weights हो सकते हैं, लेकिन Negative cycle नहीं होना चाहिए।
  • सभी vertex pairs (i, j) के लिए shortest distance निकालता है।

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

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

  • यदि i==ji == j, तो D[i][j]=0D[i][j] = 0
  • यदि ii से jj के बीच edge है, तो D[i][j]=weightD[i][j] = weight
  • नहीं है तो D[i][j]=∞D[i][j] = ∞

अब हम तीन 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 होता रहेगा जैसे:

  • k = 1: All paths through node 1
  • k = 2: All paths through node 2
  • …
  • k = n: Final shortest paths between all nodes

👉 अंतिम 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:

  • 📝 Floyd-Warshall का step-by-step Hindi PDF notes?
  • 🎥 Hindi video explanation with animated graph?
  • 🧪 A live code implementation in Python or C++?

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



You May Also Like

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

Ali Seron Jason 0

GATE CSEIT / Algorithm Analysis and Design/ Introduction to Algorithm – Understanding with real life Example

Ali Seron Jason 0

Methods of Algorithm – Independent Experimental.

Ali Seron Jason 0

Leave a Reply

Your email address will not be published. Required fields are marked *

error: