Mastering Graph Algorithms: BFS, DFS, Dijkstra, Floyd-Warshall, and Bellman-Ford in Java

Chapter 4: Floyd-Warshall Algorithm in Java

The Floyd-Warshall Algorithm is a classic dynamic programming technique used to find the shortest paths between all pairs of vertices in a graph. Unlike Dijkstra’s (which is single-source), Floyd-Warshall gives you a complete distance matrix — showing the shortest distance from every vertex to every other vertex.

This algorithm can handle negative edge weights (but not negative cycles) and works with directed or undirected graphs. It operates by progressively updating the shortest paths between all pairs using an intermediate vertex k, checking if the path i → k → j is shorter than i → j.

Though powerful, its O(V³) time complexity makes it suitable only for small to medium-sized dense graphs.

2. Floyd-Warshall Coding (with 2 Examples)

a. Syllabus-Oriented Example (All-Pairs Shortest Paths)

import java.util.*;

public class FloydWarshallExample {

    static final int INF = 99999;

    public static void floydWarshall(int[][] graph, int V) {

        int[][] dist = new int[V][V];

        // Initialize the solution matrix

        for (int i = 0; i < V; i++)

            for (int j = 0; j < V; j++)

                dist[i][j] = graph[i][j];

        // Core logic

        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] + dist[k][j] < dist[i][j])

                        dist[i][j] = dist[i][k] + dist[k][j];

                }

            }

        }

        // Output shortest path matrix

        for (int i = 0; i < V; i++) {

            System.out.println(Arrays.toString(dist[i]));

        }

    }

    public static void main(String[] args) {

        int[][] graph = {

            {0, 3, INF, 5},

            {2, 0, INF, 4},

            {INF, 1, 0, INF},

            {INF, INF, 2, 0}

        };

        floydWarshall(graph, 4);

    }

}

b. Real-World Example (Network Routing Cost Matrix)

In telecommunication or cloud networks, Floyd-Warshall helps build a routing table that shows the least-cost path between every router in the network.

// Imagine this is a cost matrix between servers or routers

// The Floyd-Warshall logic remains the same — just change node labels to represent routers (R1, R2, etc.)

import java.util.*;

public class FloydWarshallNetworkRouting {

    static final int INF = 99999;

    // Mapping router names to integer indices

    static Map<String, Integer> routerIndex = Map.of(

        "R1", 0, "R2", 1, "R3", 2, "R4", 3

    );

    static String[] routers = {"R1", "R2", "R3", "R4"};

    public static void floydWarshall(int[][] costMatrix) {

        int V = costMatrix.length;

        int[][] dist = new int[V][V];

        // Initialize distance matrix

        for (int i = 0; i < V; i++)

            for (int j = 0; j < V; j++)

                dist[i][j] = costMatrix[i][j];

        // Floyd-Warshall logic

        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] + dist[k][j] < dist[i][j])

                        dist[i][j] = dist[i][k] + dist[k][j];

                }

            }

        }

        // Display routing cost table

        System.out.println("Routing Cost Table (All-Pairs Shortest Paths):");

        System.out.print("    ");

        for (String dest : routers)

            System.out.print(dest + "   ");

        System.out.println();

        for (int i = 0; i < V; i++) {

            System.out.print(routers[i] + "  ");

            for (int j = 0; j < V; j++) {

                if (dist[i][j] == INF)

                    System.out.print("INF ");

                else

                    System.out.printf("%3d ", dist[i][j]);

            }

            System.out.println();

        }

    }

    public static void main(String[] args) {

        int[][] networkGraph = {

            {0,    5,    INF, 10},

            {INF,  0,    3,   INF},

            {INF, INF,  0,    1},

            {INF, INF, INF,  0}

        };

        floydWarshall(networkGraph);

    }

}

// For practical use, apply node mapping from router names to integer indices and back

Real-world Floyd-Warshall implementations often include a path reconstruction matrix to also return the actual paths, not just distances.

3. Pros of Floyd-Warshall Algorithm

• ✅ Finds shortest paths between all pairs in one run.
• ✅ Handles negative edge weights safely (excluding cycles).
• ✅ Simple and elegant matrix-based implementation.
• ✅ Ideal for dense graphs and network routing tables.
• ✅ Easy to extend with path reconstruction logic.

4. Cons of Floyd-Warshall Algorithm

• ❌ O(V³) time complexity — not suitable for large graphs.
• ❌ Doesn’t detect or handle negative cycles unless additional checks are added.
• ❌ High space complexity: uses O(V²) matrix.
• ❌ Not suitable for real-time pathfinding due to slowness on big graphs.
• ❌ Requires complete graph input, including INF for unreachable pairs.

5. How Floyd-Warshall Is Better Than Other Algorithms

• Compared to Dijkstra: Offers all-pairs shortest paths instead of single-source.
• Compared to Bellman-Ford: Simpler logic for dense graphs, works well when full connectivity is needed.
• Compared to BFS/DFS: Much more powerful — not just traversal, but full path optimization.

6. Best-Case Scenarios to Use Floyd-Warshall

• Routing tables in networks or distributed systems.
• Computing least-cost paths in transportation systems.
• In dense graphs where nearly every node connects to others.
• Static graphs where paths don’t change frequently.
• For academic or theoretical analysis of graph distances.

7. Applications of Floyd-Warshall Algorithm

• Telecommunication networks (e.g., cost of calling between cities).
• Shortest travel time between all airports/cities.
• Cloud infrastructure to determine optimal data transfer paths.
• Game AI path pre-processing (e.g., shortest paths between zones).
• Flight or road scheduling systems.

8. Worst-Case Scenarios to Use Floyd-Warshall

• Large sparse graphs — inefficient due to cubic time complexity.
• Graphs with negative cycles — gives incorrect results unless detected separately.
• Real-time systems needing quick updates — not ideal for frequent graph changes.
• Applications where only one source node matters — Dijkstra or Bellman-Ford is better.
• Systems with limited memory, due to O(V²) space usage.