Floyd–Warshall Algorithm
Floyd–Warshall Algorithm एक Dynamic Programming (DP) आधारित algorithm है, जिसका उपयोग weighted graph में all-pairs shortest path find करने के लिए किया जाता है।
यह algorithm यह determine करता है, कि graph के हर vertex से हर दूसरे vertex तक minimum (shortest) distance कितना है, चाहे graph directed हो या undirected।
Key Points (मुख्य बिंदु)
- यह एक Dynamic Programming (DP) algorithm है
- All-Pairs Shortest Path Problem को solve करता है
- Adjacency Matrix का उपयोग करता है
- Negative edge weights को allow करता है
- Optimal Substructure और Overlapping Subproblems पर based है
- Intermediate vertex concept use करता है
- Time Complexity : O(n³)
- Space Complexity : O(n²)
Why Floyd–Warshall Algorithm is Needed? (आवश्यकता क्यों है?)
Floyd–Warshall Algorithm की आवश्यकता All-Pairs Shortest Path (APSP) problem को solve करने के लिए होती है।
1. All-Pairs Shortest Path Requirement
- Dijkstra और Bellman-Ford केवल single source shortest path देते हैं।
- लेकिन जब हमें हर node से हर node तक shortest path चाहिए, तब Floyd–Warshall useful होता है।
2. Handles Negative Edges
- Dijkstra negative weight edges handle नहीं करता।
- Floyd–Warshall negative weight edges को handle कर सकता है।
3. Efficient for Multiple Queries
- एक बार Precompute distance matrix हो जाने पर हर node से हर node तक shortest path पूछने पर O(1) lookup possible है।
4. Simple & Reliable Algorithm
- केवल 3-level nested loop में implement होता है।
- कोई complex data structure की जरूरत नहीं।
Algorithm Steps
Step 1: Initialize distance matrix
for i = 0 to V-1
for j = 0 to V-1
if i == j then dist[i][j] = 0
else if edge(i,j) exists then dist[i][j] = weight(i,j)
else dist[i][j] = ∞
Step 2: Update using intermediate vertices
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] = dist[i][k] + dist[k][j]
Step 3: Check negative cycles (optional)
for i = 0 to V-1
if dist[i][i] < 0
print “Graph contains negative weight cycle”
Pseudocode
FloydWarshall(graph):
dist = graph matrix
for k in 0..V-1:
for i in 0..V-1:
for j in 0..V-1:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
for i in 0..V-1:
if dist[i][i] < 0:
print “Negative weight cycle exists”
return dist
Applications (अनुप्रयोग)
1. Network Routing
- Internet और computer networks में data packets को fastest route से भेजने के लिए shortest path calculation की जरूरत होती है।
- Floyd-Warshall algorithm use करके all-pairs shortest paths calculate किए जा सकते हैं।
2. Transportation & Logistics
- IRCTC train network, Delhi Metro या Flipkart/Amazon delivery network में सबसे shortest route निकालने के लिए use होता है।
3. GPS and Navigation Systems
- Google Maps, MapMyIndia, Apple Maps जैसे systems में real-time shortest path calculate करने में मदद करता है।
- Traffic, road closures, और intermediate stops को consider करके efficient path choose किया जाता है।
4. Social Networks
- Social networks जैसे LinkedIn, Facebook में shortest connection between users find करने के लिए use किया जाता है।
5. AI & Game Development
- AI में pathfinding और shortest route decision making के लिए use होता है।
Advantages (लाभ)
- All-Pairs Shortest Path Solution : Floyd-Warshall algorithm directly हर pair of vertices का shortest path calculate करता है।
- Handles Negative Weights : graph में negative edge weights हैं, तो भी algorithm correct result देता है।
- Simple Implementation : केवल 3 nested loops में implement किया जा सकता है।
- Dynamic Programming Based : यह algorithm DP concept का perfect example है – intermediate results store करके final solution निकालता है।
- Works for Dense Graphs : graph में संख्या बहुत अधिक edges हैं (dense graph), तो Floyd-Warshall सबसे efficient algorithm है।
- Useful in Real-Life Applications : Network routing, GPS navigation, logistics, social networks, AI pathfinding, bioinformatics आदि में use किया जाता है।
Limitations (सीमाएँ)
- Time Complexity O(V³) : Large graphs में slow हो जाता है।
- Space Complexity O(V²) : Distance matrix के लिए high memory requirement होती है।
- Negative Cycle Handling Limitation : Algorithm detect कर सकता है कि negative cycle है, लेकिन shortest path meaningful नहीं रहता।
- Not Suitable for Sparse Graphs : graph sparse है (few edges), तो Dijkstra या Johnson’s Algorithm ज्यादा efficient हैं।
- Not Single-Source Specific : Single-source shortest path के लिए Dijkstra या Bellman-Ford ज्यादा fast और optimized हैं।
