Floyd–Warshall Algorithm in Java: Learn with Practical Examples

Floyd–Warshall is one of the most important shortest-path algorithms in computer science. Unlike algorithms such as Dijkstra’s or Bellman–Ford, which compute shortest paths from a single source vertex, Floyd–Warshall computes the shortest path between every pair of vertices in a weighted graph.

Because many real-world systems require distances between all locations rather than just one starting point, Floyd–Warshall is widely used in transportation networks, routing systems, social network analysis, geographic information systems, and graph optimization problems.

The algorithm was independently developed by Robert Floyd and Stephen Warshall during the 1960s. It remains one of the most elegant examples of dynamic programming and is considered a foundational algorithm in graph theory.

At its core, Floyd–Warshall repeatedly considers whether introducing an intermediate vertex can improve the currently known shortest path between two vertices. By systematically evaluating every possible intermediate vertex, the algorithm gradually refines all shortest-path distances until the optimal solution is obtained.

In this article, we’ll break down how Floyd–Warshall works, implement it step by step in Java, explore negative cycle detection, and examine practical examples that demonstrate where and why it is useful.

What Is Floyd–Warshall? 🔍

Floyd–Warshall finds the shortest path between every pair of vertices in a weighted graph.

A weighted graph is a graph where each connection (edge) has an associated value such as distance, cost, travel time, profit, or latency. The goal is to determine the minimum accumulated weight between every possible pair of vertices.

The algorithm works as follows:

• Create a distance matrix
• Set the distance from each vertex to itself as 0
• Set direct edge weights in the matrix
• Initialize all missing connections as ∞ (infinity)
• Consider each vertex as a potential intermediate vertex
• Update distances whenever a shorter path is discovered through that intermediate vertex

Where:

• V = number of vertices

Floyd-Warshall example. By Dcoetzee — Own work

For every pair of vertices (i, j), Floyd–Warshall asks: “Would traveling through vertex k produce a shorter path?”. If so, update the distance.

Unlike the related Bellman–Ford algorithm, which repeatedly relaxes edges, Floyd–Warshall gradually improves an entire distance matrix until all shortest paths are known.

A useful way to visualize the algorithm is to imagine progressively allowing more vertices to participate as intermediate stops. Each iteration introduces one additional vertex that paths may pass through. By the end, every possible intermediate combination has been considered.

When Should You Use Floyd–Warshall? 🧐

Floyd–Warshall is specifically designed for situations where shortest paths are required between all pairs of vertices. Common applications include:

• Road-network analysis
• Airline route planning
• Social network analysis
• Network latency optimization
• Geographic information systems (GIS)

Unlike Dijkstra’s algorithm, which computes shortest paths from a single source vertex and must be run once per vertex to obtain all-pairs shortest paths, Floyd–Warshall computes the shortest distances between every pair of vertices in a single execution.

It achieves this by maintaining a distance matrix where each entry dist[i][j] represents the currently known shortest distance from vertex i to vertex j. The algorithm then repeatedly checks whether allowing another vertex k to act as an intermediate point produces a shorter path:

By applying this update for every combination of vertices (i, j, k), Floyd–Warshall systematically considers all possible intermediate vertices and gradually improves the distance matrix until it contains the shortest-path distance between every pair of vertices. This dynamic-programming approach is what allows the algorithm to solve the all-pairs shortest-path problem in a single run, rather than repeatedly executing a single-source algorithm.

Another important feature is its ability to work with negative edge weights, provided that no negative-weight cycles exist. In fact, Floyd–Warshall can also be used to detect negative cycles: if any diagonal entry in the final distance matrix becomes negative (dist[i][i] < 0), a negative-weight cycle is present.

The algorithm runs with a time complexity of O(V³), where:

• V = number of vertices

Its space complexity is O(V²) because it stores a distance matrix containing distances between every pair of vertices.

Because of its cubic running time, Floyd–Warshall is typically best suited for small to medium-sized dense graphs or situations where all-pairs shortest-path information is needed repeatedly after a single pre-processing step. For very large sparse graphs, running Dijkstra’s algorithm from each vertex is often more efficient.

Limitations of Floyd–Warshall 📉

Although Floyd–Warshall is elegant and relatively simple to implement, it also has several important limitations that should be considered when choosing a shortest-path algorithm.

1. Computationally Expensive

Floyd–Warshall performs three nested iterations over all vertices in the graph, resulting in a time complexity of O(V³). As the number of vertices increases, the amount of work grows very quickly. For example:

• 100 vertices → approximately 1 million operations
• 1,000 vertices → approximately 1 billion operations
• 10,000 vertices → approximately 1 trillion operations

This rapid growth makes Floyd–Warshall impractical for very large graphs, especially when real-time or near real-time results are required.

2. High Memory Usage

The algorithm stores a V × V distance matrix that contains the shortest known distance between every pair of vertices. This requires O(V²) memory. While this is manageable for small graphs, memory consumption grows significantly as the number of vertices increases. For example:

• 1,000 vertices require a matrix with 1 million entries.
• 10,000 vertices require a matrix with 100 million entries.

In large-scale systems, such as social networks or internet routing infrastructures, storing the entire matrix may become prohibitively expensive.

3. Less Suitable for Sparse Graphs

Floyd–Warshall processes every possible pair of vertices regardless of how many edges actually exist. In sparse graphs, where the number of edges is much smaller than the maximum possible number of edges, much of this computation is unnecessary. Algorithms such as Edsger W. Dijkstra can often exploit sparsity and achieve significantly better performance.

For this reason, Floyd–Warshall is generally most attractive for dense graphs, where many vertex pairs are directly or indirectly connected and the all-pairs distance matrix is genuinely useful.

4. Negative Cycles Prevent Valid Solutions

One advantage of Floyd–Warshall is its ability to handle negative edge weights, something many shortest-path algorithms cannot do. However, the algorithm cannot produce meaningful shortest-path distances when a negative-weight cycle exists. A negative cycle is a loop whose total weight is less than zero.

For example, consider a cycle with total weight −5. A path could traverse that cycle repeatedly:

A → B → C → A → B → C → ...

Each traversal reduces the total path cost by another 5 units. Since the path cost can decrease indefinitely, there is no well-defined “shortest” path.

Floyd–Warshall can detect such situations by examining the final distance matrix. If any diagonal entry becomes negative (dist[i][i] < 0), a negative cycle is reachable from that vertex.

Despite these limitations, Floyd–Warshall remains one of the most widely taught and widely used all-pairs shortest-path algorithms. Its concise dynamic-programming formulation, ability to handle negative edge weights, and straightforward implementation make it an excellent choice for small to medium-sized graphs, dense networks, and applications where shortest-path information is needed between many or all pairs of vertices.

From Theory to Practice 🛠️

Now that we understand the theory behind Floyd–Warshall, let’s see how the algorithm can be implemented in Java.

Unlike e.g. Bellman–Ford, which focuses on finding shortest paths from a single source and therefore works efficiently with an edge list, Floyd–Warshall computes the shortest paths between every pair of vertices. To do this, the algorithm repeatedly asks: “Can the path from vertex i to vertex j be improved by passing through an intermediate vertex k?"

Since this calculation must be performed for every pair (i, j), an adjacency matrix (more precisely, a distance matrix) is the most natural representation. Each cell dist[i][j] stores the shortest known distance from vertex i to vertex j, allowing the algorithm to update distances efficiently as it considers each intermediate vertex.

As the algorithm progresses, this matrix is gradually refined until it contains the shortest distances between all pairs of vertices.

1. Floyd–Warshall Graph Implementation

Let’s start with a complete Java implementation of the Floyd–Warshall algorithm. The program represents the graph as an adjacency matrix, where each cell contains either the weight of an edge or INF if no direct connection exists between two vertices.

The algorithm begins by copying this matrix into a distance matrix. It then systematically considers each vertex as a potential intermediate stop between every source and destination pair. Whenever traveling through that intermediate vertex produces a shorter path, the distance matrix is updated.

By the time all vertices have been evaluated, the distance matrix contains the shortest-path distances between every pair of vertices in the graph.

import java.util.Arrays;

public class Main {

    // A large value used to represent "no direct path"
    static final int INF = 999999;

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

        // Number of vertices in the graph
        int vertices = graph.length;

        // Distance matrix that will store the shortest
        // known distances between every pair of vertices
        int[][] dist = new int[vertices][vertices];

        // Initialize the distance matrix with the
        // original edge weights from the graph
        for (int i = 0; i < vertices; i++) {
            dist[i] = Arrays.copyOf(
                    graph[i],
                    vertices
            );
        }

        // Core idea:
        // If the shortest path from i to j passes through
        // an intermediate vertex k, then its length is:
        //
        // dist[i][k] + dist[k][j]
        //
        // If this route is shorter than the currently
        // known distance dist[i][j], update it.

        // Try every vertex k as an intermediate vertex
        for (int k = 0; k < vertices; k++) {

            // Consider every possible source vertex i
            for (int i = 0; i < vertices; i++) {

                // Consider every possible destination vertex j
                for (int j = 0; j < vertices; j++) {

                    // Ensure both subpaths exist and
                    // check whether going through k
                    // produces a shorter path
                    if (dist[i][k] != INF &&
                        dist[k][j] != INF &&
                        dist[i][k] + dist[k][j]
                                < dist[i][j]) {

                        // Update the shortest known distance
                        dist[i][j] =
                                dist[i][k]
                                + dist[k][j];
                    }
                }
            }
        }

        // Print the final all-pairs shortest-path matrix
        System.out.println(
                "Shortest-path matrix:"
        );

        for (int[] row : dist) {
            System.out.println(
                    Arrays.toString(row)
            );
        }
    }

    public static void main(String[] args) {

        // Adjacency matrix representation:
        // graph[i][j] = weight of edge i -> j
        // INF means there is no direct edge
        int[][] graph = {
                {0,   3,   INF, 7},
                {8,   0,   2,   INF},
                {5,   INF, 0,   1},
                {2,   INF, INF, 0}
        };

        // Compute shortest paths between all pairs of vertices
        floydWarshall(graph);
    }
}

// Output:
// Shortest-path matrix:
// [0, 3, 5, 6]
// [5, 0, 2, 3]
// [3, 6, 0, 1]
// [2, 5, 7, 0]

This implementation showcases the three fundamental stages of the Floyd–Warshall algorithm:

• Distance matrix initialization copies the graph’s edge weights into a working matrix.
• Intermediate-vertex evaluation considers each vertex as a possible waypoint between all pairs of vertices.
• Shortest-path relaxation updates distances whenever a shorter path is discovered through an intermediate vertex.

After the algorithm completes, the resulting matrix contains the shortest distances between every pair of vertices, making Floyd–Warshall one of the most elegant solutions to the all-pairs shortest path problem.

2. Understanding the Dynamic Programming Update

The core of the Floyd–Warshall algorithm is a dynamic programming recurrence. For each intermediate vertex k, the algorithm asks a simple question: “Is the path from i to j shorter if we travel through k?”

This idea is implemented with the following update:

if (dist[i][k] + dist[k][j]
        < dist[i][j]) {
    dist[i][j] =
            dist[i][k]
            + dist[k][j];
}

For example, suppose we know:

• A → B = 4
• B → C = 3
• A → C = 10

When considering B as an intermediate vertex, the algorithm discovers an alternative route from A to C:

A → B → C = 4 + 3 = 7

Since 7 is less than the current distance of 10, the algorithm updates the distance from A to C to 7.

This update is performed for every pair of vertices (i, j) and every possible intermediate vertex k. By repeatedly refining the distance matrix in this way, the algorithm gradually uncovers the shortest paths between all pairs of vertices.

3. Negative Cycle Detection

Floyd–Warshall can also detect negative-weight cycles by examining the diagonal entries of the distance matrix after the algorithm completes:

for (int i = 0; i < vertices; i++) {
    if (dist[i][i] < 0) {
        System.out.println(
                "Negative cycle detected!"
        );
        return;
    }
}

Initially, every diagonal entry dist[i][i] is 0 because the cost of traveling from a vertex to itself is zero. During the algorithm, distances are updated whenever a shorter path is discovered.

If a negative-weight cycle is reachable from vertex i, the algorithm will eventually find a path that starts at i, traverses the cycle, and returns to i with a total cost less than zero. As a result, dist[i][i] becomes negative.

Therefore, after all updates are complete:

• dist[i][i] == 0 means no negative cycle has affected vertex i.
• dist[i][i] < 0 indicates that a negative-weight cycle is reachable from vertex i.

A negative value on the diagonal is a clear signal that the graph contains a negative-weight cycle and that some shortest paths are undefined, since repeatedly traversing the cycle can reduce the path cost indefinitely.

4. Path Reconstruction

In many real-world applications, knowing only the shortest distance is not enough — we also need to reconstruct the actual path between two vertices. The Floyd–Warshall algorithm can be extended to support this by maintaining an additional next matrix. We define:

int[][] next = new int[vertices][vertices];

The purpose of next[i][j] is to store the next vertex to visit when moving from vertex i to vertex j along the currently known shortest path. In other words, it acts as a routing table that tells us the first step to take from i toward j.

Whenever a shorter path from i to j is found via an intermediate vertex k, we update both the distance and the path information:

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

The distance update records the new shortest path length, while the next update ensures that the routing information follows the same path structure.

After the algorithm finishes, the next matrix can be used to reconstruct the full shortest path between any two vertices. Starting from the source vertex, we repeatedly follow the entries stored in next until the destination is reached.

The following complete example computes all-pairs shortest paths and reconstructs the shortest route from vertex 0 to vertex 2.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    static final int INF = 999999;

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

        int vertices = graph.length;

        int[][] dist = new int[vertices][vertices];
        int[][] next = new int[vertices][vertices];

        // Initialize distance and next matrices
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {

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

                if (i == j) {
                    next[i][j] = i;
                }
                else if (graph[i][j] != INF) {
                    next[i][j] = j;
                }
                else {
                    next[i][j] = -1;
                }
            }
        }

        // Floyd–Warshall algorithm
        for (int k = 0; k < vertices; k++) {
            for (int i = 0; i < vertices; i++) {
                for (int j = 0; j < vertices; 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];

                        next[i][j] =
                                next[i][k];
                    }
                }
            }
        }

        // Print shortest-path matrix
        System.out.println("Shortest-path matrix:");

        for (int[] row : dist) {
            System.out.println(Arrays.toString(row));
        }

        // Example: reconstruct path from 0 to 2
        List<Integer> path =
                reconstructPath(0, 2, next);

        System.out.println(
                "\nShortest path from 0 to 2: "
                + path
        );

        System.out.println(
                "Distance: "
                + dist[0][2]
        );
    }

    public static List<Integer> reconstructPath(
            int start,
            int end,
            int[][] next) {

        List<Integer> path = new ArrayList<>();

        if (next[start][end] == -1) {
            return path;
        }

        int current = start;
        path.add(current);

        while (current != end) {
            current = next[current][end];
            path.add(current);
        }

        return path;
    }

    public static void main(String[] args) {

        int[][] graph = {
                {0,   3,   INF, 7},
                {8,   0,   2,   INF},
                {5,   INF, 0,   1},
                {2,   INF, INF, 0}
        };

        floydWarshall(graph);
    }
}

// Output:
// Shortest-path matrix:
// [0, 3, 5, 6]
// [5, 0, 2, 3]
// [3, 6, 0, 1]
// [2, 5, 7, 0]

// Shortest path from 0 to 2: [0, 1, 2]
// Distance: 5

By maintaining the next matrix alongside the distance matrix, the Floyd–Warshall algorithm becomes more than a shortest-distance algorithm. It can also return the exact sequence of vertices that forms each shortest path, making it useful for routing systems, network analysis, navigation software, and many other practical applications.

5. Object-Oriented Implementation

The Floyd–Warshall algorithm can be cleanly implemented using an object-oriented approach in Java. In this design, the Graph class encapsulates the adjacency matrix and provides methods for constructing the graph and computing shortest paths between all pairs of vertices.

This structure makes the algorithm easier to manage, reuse, and extend, especially when working with larger or more complex graph-based systems.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Graph {

    // A large constant used to represent the absence of a direct edge
    static final int INF = 999999;

    private final int vertices;
    private final int[][] matrix;

    // Stores shortest distances after Floyd–Warshall
    private int[][] dist;

    // Stores path reconstruction information
    private int[][] next;

    // Initializes the graph with INF values and 0 on the diagonal
    public Graph(int vertices) {
        this.vertices = vertices;
        matrix = new int[vertices][vertices];

        for (int i = 0; i < vertices; i++) {
            Arrays.fill(matrix[i], INF);
            matrix[i][i] = 0;
        }
    }

    // Adds a directed weighted edge to the graph
    public void addEdge(int source, int destination, int weight) {
        matrix[source][destination] = weight;
    }

    // Computes shortest paths between all pairs using Floyd–Warshall
    public void floydWarshall() {

        dist = new int[vertices][vertices];
        next = new int[vertices][vertices];

        // Initialize distance and path matrices
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {

                dist[i][j] = matrix[i][j];

                if (i == j) {
                    next[i][j] = i;
                }
                else if (matrix[i][j] != INF) {
                    next[i][j] = j;
                }
                else {
                    next[i][j] = -1;
                }
            }
        }

        // Floyd–Warshall algorithm
        for (int k = 0; k < vertices; k++) {
            for (int i = 0; i < vertices; i++) {
                for (int j = 0; j < vertices; 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];

                        // Update path information
                        next[i][j] = next[i][k];
                    }
                }
            }
        }

        // Print shortest-path matrix
        System.out.println("Shortest-path matrix:");

        for (int[] row : dist) {
            System.out.println(Arrays.toString(row));
        }
    }

    // Reconstructs the shortest path between two vertices
    public List<Integer> getPath(int start, int end) {

        if (next == null) {
            throw new IllegalStateException(
                    "Run floydWarshall() first."
            );
        }

        List<Integer> path = new ArrayList<>();

        if (next[start][end] == -1) {
            return path;
        }

        int current = start;
        path.add(current);

        while (current != end) {
            current = next[current][end];
            path.add(current);
        }

        return path;
    }

    // Returns the shortest distance between two vertices
    public int getDistance(int start, int end) {

        if (dist == null) {
            throw new IllegalStateException(
                    "Run floydWarshall() first."
            );
        }

        return dist[start][end];
    }
}

public class Main {

    public static void main(String[] args) {

        Graph graph = new Graph(4);

        graph.addEdge(0, 1, 3);
        graph.addEdge(0, 3, 7);

        graph.addEdge(1, 0, 8);
        graph.addEdge(1, 2, 2);

        graph.addEdge(2, 0, 5);
        graph.addEdge(2, 3, 1);

        graph.addEdge(3, 0, 2);

        graph.floydWarshall();

        System.out.println(
                "\nShortest path from 0 to 2: "
                + graph.getPath(0, 2)
        );

        System.out.println(
                "Distance: "
                + graph.getDistance(0, 2)
        );
    }
}

// Output:
// Shortest-path matrix:
// [0, 3, 5, 6]
// [5, 0, 2, 3]
// [3, 6, 0, 1]
// [2, 5, 7, 0]

// Shortest path from 0 to 2: [0, 1, 2]
// Distance: 5

This implementation demonstrates how the Floyd–Warshall algorithm can be structured in a clean and modular way using object-oriented principles. The adjacency matrix serves as the core data representation, while the algorithm operates on a separate working copy to compute shortest paths without modifying the original graph.

By combining simplicity with clear separation of responsibilities, this approach provides a solid foundation for further enhancements such as path reconstruction, support for undirected graphs, or integration into larger graph-processing systems.

Practical Examples 💡

The Floyd–Warshall algorithm is widely used in systems where we need to compute shortest paths between every pair of nodes in a network. Unlike single-source algorithms (such as Dijkstra), which compute paths from one starting point, Floyd–Warshall produces a complete all-pairs shortest path table. This makes it especially useful in applications where:

• The same network is queried repeatedly
• Fast response time is important after pre-processing
• Relationships between all entities matter, not just one

Although the algorithm itself runs in O(n3)O(n³)O(n3), its real advantage is that once it finishes, any distance query can be answered in constant time O(1).

Below are some practical real-world use cases.

1. Airline Route Planning

Airline networks are a classic example of a weighted graph. In this model:

• Airports are represented as vertices.
• Direct flights are represented as edges.
• Edge weights can represent distance, flight duration, fuel consumption, or operating cost.

Airlines often need to determine the most efficient route between any two airports in their network. Because passengers may travel between thousands of origin–destination pairs, computing shortest paths on demand can be expensive. Floyd–Warshall solves this problem by precomputing the optimal route between every pair of airports in a single execution.

Graph airline = new Graph(4);

// Direct flight routes between airports
airline.addEdge(0, 1, 500);   // Airport 0 → 1
airline.addEdge(1, 2, 300);   // Airport 1 → 2
airline.addEdge(2, 3, 250);   // Airport 2 → 3
airline.addEdge(0, 3, 1500);  // Direct but expensive route

// Compute all-pairs shortest paths
airline.floydWarshall();

System.out.println(
        "\nShortest path from 0 to 3: "
        + airline.getPath(0, 3)
);

System.out.println(
        "Distance: "
        + airline.getDistance(0, 3)
);

// Output:
// Shortest-path matrix:
// [0, 500, 800, 1050]
// [999999, 0, 300, 550]
// [999999, 999999, 0, 250]
// [999999, 999999, 999999, 0]

// Shortest path from 0 to 3: [0, 1, 2, 3]
// Distance: 1050

At first glance, the direct flight from Airport 0 to Airport 3 appears to be the obvious choice because it requires only one flight. However, Floyd–Warshall evaluates all possible intermediate airports and discovers a cheaper route:

0 → 1 → 2 → 3

Total cost:
500 + 300 + 250 = 1050

This is significantly less expensive than the direct route: 0 -> 3 = 1500. As a result, the algorithm updates the shortest distance between Airports 0 and 3 from 1500 to 1050.

2. Social Network Analysis

Social networks such as messaging platforms, professional networking sites, and online communities can be modeled as graphs:

• Users are represented as vertices.
• Friendships, follows, or connections are represented as edges.
• Edge weights can represent the strength of a relationship, interaction frequency, or simply the number of steps required to reach another user.

One common problem in social network analysis is determining how closely two users are connected. Even if two users are not directly linked, they may still be connected through mutual friends or intermediate contacts.

Floyd–Warshall helps solve this problem by computing the shortest connection path between every pair of users in the network.

Graph social = new Graph(5);

// Friendship connections
social.addEdge(0, 1, 1);
social.addEdge(1, 2, 1);
social.addEdge(2, 3, 1);
social.addEdge(3, 4, 1);
social.addEdge(0, 4, 10);

// Compute all-pairs shortest paths
social.floydWarshall();

// Output:
// Shortest-path matrix:
// [0, 1, 2, 3, 4]
// [999999, 0, 1, 2, 3]
// [999999, 999999, 0, 1, 2]
// [999999, 999999, 999999, 0, 1]
// [999999, 999999, 999999, 999999, 0]

// Shortest path from 0 to 4: [0, 1, 2, 3, 4]
// Distance: 4

At first,User 0 appears to have a direct connection to User 4 with a distance of 10. However, Floyd–Warshall evaluates all possible intermediate users and discovers a much shorter path:

0 → 1 → 2 → 3 → 4

Total distance:
1 + 1 + 1 + 1 = 4

Since 4 < 10, the algorithm updates the shortest distance between Users 0 and 4 from 10 to 4.

This reveals that although the users are not strongly connected directly, they are relatively close through a chain of mutual connections.

3. Transportation Systems

Modern transportation networks consist of many interconnected locations, including train stations, bus stops, airports, and transit hubs. These networks can be naturally modeled as weighted graphs:

• Vertices represent stations, stops, or terminals.
• Edges represent direct routes between locations.
• Edge weights typically represent travel time, distance, ticket cost, or expected transit delay.

Transportation planners and navigation systems frequently need to answer questions such as:

• What is the fastest route between two stations?
• How long will a journey take?
• Which transfer combination minimizes travel time?

Rather than calculating routes from scratch every time a query is made, Floyd–Warshall can precompute the shortest travel times between all pairs of locations in a single execution.

Graph transport = new Graph(4);

// Travel times between stations
transport.addEdge(0, 1, 10);  // Station 0 → 1
transport.addEdge(1, 2, 15);  // Station 1 → 2
transport.addEdge(0, 3, 50);  // Direct but slower route
transport.addEdge(2, 3, 10);  // Station 2 → 3

// Compute all-pairs shortest travel times
transport.floydWarshall();

// Output:
// Shortest-path matrix:
// [0, 10, 25, 35]
// [999999, 0, 15, 25]
// [999999, 999999, 0, 10]
// [999999, 999999, 999999, 0]

// Shortest path from 0 to 3: [0, 1, 2, 3]
// Distance: 35

The direct route fromStation 0 toStation 3 takes 50 minutes.

0 → 3 = 50

However, Floyd–Warshall evaluates alternative routes through intermediate stations and discovers a faster journey:

0 → 1 → 2 → 3

Total travel time:
10 + 15 + 10 = 35

Since 35 minutes is shorter than 50 minutes, the algorithm updates the shortest travel time between Stations 0 and 3.

Conclusion 📣

Floyd–Warshall is one of the most elegant and versatile shortest-path algorithms in graph theory. By using a dynamic programming approach, it efficiently computes the shortest distance between every pair of vertices in a weighted graph, making it fundamentally different from single-source algorithms such as Dijkstra’s or Bellman–Ford.

Throughout this article, we explored how the algorithm works, examined its core distance-update recurrence, implemented it in Java, added support for path reconstruction, and extended the solution using object-oriented design principles. We also saw how Floyd–Warshall can detect negative-weight cycles and how it can be applied to practical problems such as airline route planning, social network analysis, and transportation systems.

The algorithm’s greatest strength is its ability to provide complete all-pairs shortest-path information after a single pre-processing step. Once the distance matrix has been computed, shortest-path queries can be answered instantly, making Floyd–Warshall particularly valuable in applications where the same network is queried repeatedly.

However, this convenience comes at a cost. With a time complexity of O(V³) and a space complexity of O(V²), Floyd–Warshall is best suited for small to medium-sized graphs, dense networks, and scenarios where all-pairs shortest-path information is required. For very large or sparse graphs, algorithms such as Dijkstra’s often provide better scalability.

Despite being developed more than half a century ago, Floyd–Warshall remains a cornerstone of graph algorithms and an excellent example of dynamic programming in practice. Its concise implementation, support for negative edge weights, ability to reconstruct shortest paths, and applicability across a wide range of real-world problems ensure that it continues to be an essential tool in every software engineer’s and computer scientist’s toolkit.

Whether you’re building a routing engine, analyzing network connectivity, optimizing transportation systems, or simply learning graph algorithms, understanding Floyd–Warshall provides valuable insight into one of the most influential algorithms in computer science.

Thanks for reading! Please give this article a clap and follow me if you enjoyed it 😃