Floyd-Warshall Algorithm

Generated on 2025-07-10 01:58:53 Algorithm Cheatsheet for Technical Interviews

---

Floyd-Warshall Algorithm Cheatsheet

1. Quick Overview

• What is it? A dynamic programming algorithm for finding the shortest paths between all pairs of vertices in a weighted graph. It can handle both directed and undirected graphs, and edges with positive or negative weights (but no negative cycles).
• When to use it?
  • You need to find the shortest paths between every pair of vertices.
  • The graph is relatively small (up to a few hundred vertices) due to its cubic time complexity.
  • Negative edge weights are present (but no negative cycles). Dijkstra’s algorithm won’t work reliably in this case for all pairs.
  • Detecting negative cycles is a requirement.
• Key Idea: Iteratively considers each vertex k as a potential intermediate vertex in the shortest path between every pair of vertices i and j.

2. Time & Space Complexity

Aspect	Complexity	Explanation
Time	O(V3)	Three nested loops, each iterating up to the number of vertices (V).
Space	O(V2)	Stores the shortest path distances between all pairs of vertices in a V x V matrix. In-place modifications are possible, so it can sometimes be O(1) if you don’t need to preserve the original matrix.

3. Implementation

Python:

import sys

def floyd_warshall(graph):
    """
    Finds the shortest paths between all pairs of vertices in a graph using the Floyd-Warshall algorithm.

    Args:
        graph: A list of lists representing the adjacency matrix of the graph.
               graph[i][j] represents the weight of the edge from vertex i to vertex j.
               Use float('inf') for no edge and 0 for self loops
    Returns:
        A list of lists representing the shortest path distances between all pairs of vertices.
        Returns None if a negative cycle is detected.
    """
    V = len(graph)
    dist = [row[:] for row in graph]  # Create a copy to avoid modifying the original

    # Iterate through all vertices as intermediate nodes
    for k in range(V):
        # Iterate through all pairs of vertices
        for i in range(V):
            for j in range(V):
                # If vertex k is on the shortest path from i to j, update dist[i][j]
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # Check for negative cycles
    for i in range(V):
        if dist[i][i] < 0:
            print("Negative cycle detected")
            return None

    return dist

# Example Usage
if __name__ == '__main__':
    graph = [
        [0,   5,  float('inf'), 10],
        [float('inf'), 0,   3, float('inf')],
        [float('inf'), float('inf'), 0,   1],
        [float('inf'), float('inf'), float('inf'), 0]
    ]

    result = floyd_warshall(graph)

    if result:
        print("Shortest path distances:")
        for row in result:
            print(row)

Java:

import java.util.Arrays;

class FloydWarshall {

    public static int[][] floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // Initialize the distance matrix with the given graph
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // Iterate through all vertices as intermediate nodes
        for (int k = 0; k < V; k++) {
            // Iterate through all pairs of vertices
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // If vertex k is on the shortest path from i to j, update dist[i][j]
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
                        dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // Check for negative cycles
        for (int i = 0; i < V; i++) {
            if (dist[i][i] < 0) {
                System.out.println("Negative cycle detected");
                return null;
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int INF = Integer.MAX_VALUE;
        int[][] graph = {
            {0,   5,  INF, 10},
            {INF, 0,   3, INF},
            {INF, INF, 0,   1},
            {INF, INF, INF, 0}
        };

        int[][] result = floydWarshall(graph);

        if (result != null) {
            System.out.println("Shortest path distances:");
            for (int[] row : result) {
                System.out.println(Arrays.toString(row));
            }
        }
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9; // A large number to represent infinity

vector<vector<int>> floydWarshall(vector<vector<int>>& graph) {
    int V = graph.size();
    vector<vector<int>> dist(V, vector<int>(V));

    // Initialize the distance matrix with the given graph
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Iterate through all vertices as intermediate nodes
    for (int k = 0; k < V; k++) {
        // Iterate through all pairs of vertices
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // If vertex k is on the shortest path from i to j, update dist[i][j]
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Check for negative cycles
    for (int i = 0; i < V; i++) {
        if (dist[i][i] < 0) {
            cout << "Negative cycle detected" << endl;
            return {}; // Return an empty vector to indicate failure
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0,   5,  INF, 10},
        {INF, 0,   3, INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    };

    vector<vector<int>> result = floydWarshall(graph);

    if (!result.empty()) {
        cout << "Shortest path distances:" << endl;
        for (const auto& row : result) {
            for (int val : row) {
                cout << val << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

Explanation:

1. Initialization: The dist matrix is initialized with the edge weights from the input graph. INF (infinity) represents no direct edge.
2. Iteration: The core of the algorithm is the three nested loops. The outer loop iterates through all vertices k, considering each as a potential intermediate node. The inner loops iterate through all pairs of vertices i and j.
3. Relaxation: Inside the inner loops, dist[i][j] is updated with the minimum of its current value and the distance from i to k plus the distance from k to j. This step essentially checks if going through vertex k results in a shorter path between i and j.
4. Negative Cycle Detection: After the main loops, the algorithm checks for negative cycles. If dist[i][i] is negative for any vertex i, it indicates the presence of a negative cycle. This is because the shortest path from a vertex to itself should always be 0 if there are no negative cycles.

4. Common Patterns

• All-Pairs Shortest Paths: The primary use case is finding the shortest paths between every pair of vertices.
• Transitive Closure: Determine if there is a path between any two vertices. Modify the algorithm to use boolean values (True/False) instead of distances. dist[i][j] becomes True if there’s a path from i to j.
• Detecting Negative Cycles: As shown in the implementation, the algorithm can detect negative cycles.
• Finding the Diameter of a Graph: After running Floyd-Warshall, the diameter of the graph is the maximum value in the resulting distance matrix.
• Reachability Analysis: determining which nodes can be reached from other nodes.

5. Pro Tips

• Infinity Representation: Choose a sufficiently large value for infinity (INF) that avoids overflow issues when adding distances. sys.maxsize in Python or Integer.MAX_VALUE in Java can be used, but be careful about adding to them (use a smaller value, like 1e9).
• In-Place Modification: If you don’t need to preserve the original graph, you can modify the input graph matrix directly to save space. However, be aware that this will alter the original data.
• Negative Cycle Handling: If a negative cycle is detected, the shortest path distances are not well-defined, and the algorithm should return an error or indicate the presence of the cycle.
• Optimization for Sparse Graphs: Floyd-Warshall is not optimal for sparse graphs. For sparse graphs, Johnson’s algorithm (which combines Dijkstra’s and Bellman-Ford) might be more efficient.
• Order of Loops: The order of the loops (k, i, j) is crucial for the algorithm to work correctly. k (intermediate node) must be the outermost loop.

6. Practice Problems

1. LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance: Use Floyd-Warshall to compute the shortest paths between all cities. Then, for each city, count the number of cities reachable within the given distance threshold.
2. LeetCode 743. Network Delay Time: While Dijikstra is faster for single source, Floyd-Warshall can solve this problem. Treat the source node as the starting point and find the maximum shortest path to all other nodes.
3. Codeforces 11D - A Simple Task: (More challenging) Requires finding the number of cycles of length at least 3 in a graph. Floyd-Warshall can be adapted for this, though it’s not a direct application. This problem is more about dynamic programming with bitmasking to track visited nodes.

7. Templates

These templates provide starting points for implementing Floyd-Warshall in different languages. They include basic structure and comments to guide your implementation.

C++ Template:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9; // Define infinity

vector<vector<int>> floydWarshallTemplate(vector<vector<int>>& graph) {
    int V = graph.size();
    vector<vector<int>> dist = graph; //Initialize

    // Iterate through all possible intermediate nodes
    for (int k = 0; k < V; ++k) {
        // Iterate through all possible source nodes
        for (int i = 0; i < V; ++i) {
            // Iterate through all possible destination nodes
            for (int j = 0; j < V; ++j) {
                // Relaxation step: check if going through k provides a shorter path
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // Negative cycle detection (optional)
    for (int i = 0; i < V; ++i) {
        if (dist[i][i] < 0) {
            cout << "Negative cycle detected!" << endl;
            return {}; // Or some other error indicator
        }
    }

    return dist;
}

int main() {
    // Example usage
    vector<vector<int>> graph = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };

    vector<vector<int>> result = floydWarshallTemplate(graph);

    if (!result.empty()) {
        cout << "Shortest distances between all pairs of vertices:" << endl;
        for (const auto& row : result) {
            for (int val : row) {
                cout << (val == INF ? "INF" : to_string(val)) << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

Python Template:

import sys

def floyd_warshall_template(graph):
    """
    Floyd-Warshall algorithm template.

    Args:
        graph: Adjacency matrix of the graph (list of lists).
               Use float('inf') for no edge.

    Returns:
        Shortest path distances between all pairs, or None if negative cycle detected.
    """
    V = len(graph)
    dist = [row[:] for row in graph]  # Copy the graph

    # Iterate through all possible intermediate nodes
    for k in range(V):
        # Iterate through all possible source nodes
        for i in range(V):
            # Iterate through all possible destination nodes
            for j in range(V):
                # Relaxation step: check if going through k provides a shorter path
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # Negative cycle detection (optional)
    for i in range(V):
        if dist[i][i] < 0:
            print("Negative cycle detected!")
            return None

    return dist

if __name__ == '__main__':
    # Example usage
    graph = [
        [0, 3, float('inf'), 7],
        [8, 0, 2, float('inf')],
        [5, float('inf'), 0, 1],
        [2, float('inf'), float('inf'), 0]
    ]

    result = floyd_warshall_template(graph)

    if result:
        print("Shortest distances between all pairs of vertices:")
        for row in result:
            print([("INF" if x == float('inf') else x) for x in row])

Java Template:

import java.util.Arrays;

class FloydWarshallTemplate {

    public static int[][] floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // Initialize dist matrix with graph values
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // Iterate through all possible intermediate nodes
        for (int k = 0; k < V; k++) {
            // Iterate through all possible source nodes
            for (int i = 0; i < V; i++) {
                // Iterate through all possible destination nodes
                for (int j = 0; j < V; j++) {
                    // Relaxation step: check if going through k provides a shorter path
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // Negative cycle detection (optional)
        for (int i = 0; i < V; i++) {
            if (dist[i][i] < 0) {
                System.out.println("Negative cycle detected!");
                return null; // Or some other error indication
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        // Example usage
        int INF = Integer.MAX_VALUE;
        int[][] graph = {
                {0, 3, INF, 7},
                {8, 0, 2, INF},
                {5, INF, 0, 1},
                {2, INF, INF, 0}
        };

        int[][] result = floydWarshall(graph);

        if (result != null) {
            System.out.println("Shortest distances between all pairs of vertices:");
            for (int[] row : result) {
                System.out.println(Arrays.toString(row).replaceAll(Integer.MAX_VALUE + "", "INF"));
            }
        }
    }
}

These templates provide a basic structure. Remember to adapt the INF value and error handling (negative cycle detection) as needed for your specific problem.