🌍 Floyd-Warshall Algorithm – Comprehensive Study Guide

The **Floyd-Warshall Algorithm** is a **dynamic programming technique** that finds the **shortest path between all pairs of vertices** in a graph.

⚡ Why Use Floyd-Warshall?

• ✅ **Computes shortest paths between all node pairs.**
• 📡 **Works for graphs with negative weights (but no negative cycles).**
• 🚀 **Used in network routing and GPS navigation.**
• 🔍 **Can detect negative weight cycles efficiently.**

📌 How Does Floyd-Warshall Work?

The algorithm **iteratively improves** the shortest paths by considering intermediate vertices between each pair of nodes.

📌 Step-by-Step Execution

1. ✅ **Initialize** the distance matrix with given edge weights.
2. 📌 Use **three nested loops** to iteratively update the shortest distances.
3. 🔍 If `dist[i][j] > dist[i][k] + dist[k][j]`, update the shortest path.
4. 🚨 If `dist[i][i] < 0` for any vertex, a **negative cycle** exists.

🛠️ Floyd-Warshall Algorithm Implementation

🔄 **1. Floyd-Warshall Algorithm (O(V³))**

                #include 
                using namespace std;
            
                const int INF = 1e9; // Large number to represent infinity
            
                void floydWarshall(vector> &dist, int V) {
                    for (int k = 0; k < V; k++) {
                        for (int i = 0; i < V; i++) {
                            for (int j = 0; j < V; j++) {
                                if (dist[i][k] < INF && dist[k][j] < INF) {
                                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                                }
                            }
                        }
                    }
                }
            
                int main() {
                    int V = 4;
                    vector> dist = {
                        {0, 3, INF, 5},
                        {2, 0, INF, 4},
                        {INF, 1, 0, INF},
                        {INF, INF, 2, 0}
                    };
            
                    floydWarshall(dist, V);
            
                    cout << "Shortest Distance Matrix:\n";
                    for (auto &row : dist) {
                        for (int val : row)
                            cout << (val == INF ? "INF" : to_string(val)) << " ";
                        cout << endl;
                    }
                    return 0;
                }
                

🚨 Handling Negative Weight Cycles

The Floyd-Warshall algorithm detects **negative weight cycles** by checking the diagonal of the distance matrix.

                for (int i = 0; i < V; i++) {
                    if (dist[i][i] < 0) {
                        cout << "Negative Cycle Detected!\n";
                    }
                }
                

⚖️ Floyd-Warshall vs Dijkstra vs Bellman-Ford

⏳ Time Complexity Analysis

• ✅ **Best Case:** O(V³) – Fully connected graph.
• ⚡ **Worst Case:** O(V³) – Sparse graph.

🌍 Real-World Applications of Floyd-Warshall

• 📡 **Network Routing Protocols** – Finding shortest routes between all nodes.
• 📊 **Social Network Analysis** – Measuring distances between users.
• 🔗 **AI & Game Development** – Pathfinding in multi-agent systems.
• 🚗 **GPS & Traffic Navigation Systems** – Optimal route calculations.

🔗 Next Topics

• 📡 Dijkstra’s Algorithm
• 🔍 Bellman-Ford Algorithm
• 🌉 Graph Traversal Techniques