Floyd-Warshall Algorithm for Shortest Path in Weighted Graphs

Imagine you're running a logistics company, and you need to determine the most efficient delivery routes for your packages between multiple locations. Instead of calculating each possible route manually, the Floyd-Warshall Algorithm helps you find the shortest paths between all pairs of intersections. This is just one of its many real-world advantages.

In this blog, you’ll learn about the Floyd-Warshall Algorithm, its step-by-step process, and how to implement it. You'll explore its core principles, practical applications, and why it’s crucial for solving shortest path problems.

How the Floyd-Warshall Algorithm Works? Key Insights

The Floyd Warshall Algorithm is a versatile tool for solving the all-pairs shortest path problem in weighted graphs. Unlike algorithms like Dijkstra or Bellman-Ford, which focus on finding the shortest path from a single source, Floyd Warshall computes the shortest paths between every pair of vertices. 

It's a dynamic programming algorithm, meaning it incrementally builds the shortest paths by considering each vertex as an intermediate point and updating the distances step by step. 

While the algorithm is highly efficient for dense graphs, it doesn’t work with graphs that contain negative weight cycles, which would lead to incorrect results.

A Step-by-Step Breakdown of the Algorithm with Example

Let’s use a real-life example to better understand the Floyd-Warshall Algorithm. Imagine you’re running a logistics company, and you need to find the best delivery route for packages to multiple locations within a city.

The city can be represented as a graph, where each intersection or location is a vertex, and the streets or roads between these intersections are the edges. Each street has a distance, which represents the weight or cost of traveling that road. Your goal is to figure out the shortest route between every pair of intersections.

Instead of calculating the shortest route for each pair individually, the Floyd-Warshall Algorithm helps you efficiently find the shortest path between all pairs of intersections. This is done by iteratively refining the possible paths between intersections, ensuring that the shortest route is found at the end. 

Step 1: Initialize the Distance Matrix

To start, we create a distance matrix that holds the initial distances between each pair of intersections (vertices). The matrix will represent all possible direct routes between intersections. If there is no direct route between two intersections, we set the distance as infinity.

Here’s an example of how the initial matrix might look for a city with 4 intersections (A, B, C, D):

Graphical representation:

    A ------(4)-----> B
    |                 |
    (∞)               (1)
    |                 |
    v                 v
    C <------(3)------ D
    |
    (2)
    |
    v
    A

Matrix representation:

    A   B   C   D
A   0   4   ∞   5
B   ∞   0   1   ∞
C   2   ∞   0   3
D   ∞   ∞   1   0

• A to B = 4 (direct path)
• B to C = 1 (direct path)
• C to D = 3 (direct path)
• If there is no direct connection, the distance is marked as ∞.

Step 2: Consider Each Vertex as an Intermediate Vertex

Now, you start considering each intersection as an intermediate point (k) to potentially shorten the paths between other intersections.

First Iteration: Consider A (Vertex 1) as the Intermediate Vertex

In each iteration, you check whether paths through the intermediate vertex offer a shorter route than the current path.

A to C: Currently, there's no direct path from A to C (∞). However, if you go A → B → C, the distance would be 4 + 1 = 5, which is shorter than ∞. So, update the matrix for A to C to 5.

After the first iteration, your distance matrix looks like this:

    A   B   C   D
A   0   4   5   5
B   ∞   0   1   ∞
C   2   ∞   0   3
D   ∞   ∞   1   0

Second Iteration: Consider B (Vertex 2) as the Intermediate Vertex

A to C: The current shortest distance from A to C is 5. Through B, the route A → B → C gives 4 + 1 = 5, so no update is needed.

After this iteration, the matrix remains the same:

    A   B   C   D
A   0   4   5   5
B   ∞   0   1   ∞
C   2   ∞   0   3
D   ∞   ∞   1   0

Third Iteration: Consider C (Vertex 3) as the Intermediate Vertex

A to D: The current shortest distance from A to D is 5. If you go A → C → D, you get 5 + 3 = 8, which is longer than 5. No update needed.

After this iteration, the matrix still looks the same:

    A   B   C   D
A   0   4   5   5
B   ∞   0   1   ∞
C   2   ∞   0   3
D   ∞   ∞   1   0

Fourth Iteration: Consider D (Vertex 4) as the Intermediate Vertex

A to B: The direct distance from A to B is 4, and no shorter path is found via D. No update is needed.

After completing the final iteration, the distance matrix remains unchanged.

    A   B   C   D
A   0   4   5   5
B   ∞   0   1   ∞
C   2   ∞   0   3
D   ∞   ∞   1   0

Now that all intermediate vertices have been considered, the matrix contains the shortest paths between all pairs of intersections in the city. 

The Floyd-Warshall Algorithm is an effective tool for solving routing problems where you need to know the shortest path between multiple points, especially in transportation, logistics, or even network optimization scenarios.

The ability to compute shortest paths efficiently is vital for handling complex networks and graphs—let’s dive into how the algorithm works.

Now, let’s dive into how you can implement the Floyd-Warshall Algorithm in C.

Program for Implementing the Floyd-Warshall Algorithm: A Walkthrough for Beginners

Implementing the Floyd Warshall Algorithm involves initializing a distance matrix with direct distances between vertices, setting ∞ for non-existing edges. The algorithm then iterates through each vertex, considering it as an intermediate node, and updates the matrix if a shorter path is found between any two vertices. 

This process repeats for all vertices, ensuring the matrix contains the shortest paths between all pairs. Using nested loops, the algorithm efficiently computes all-pairs shortest paths, making it ideal for dense graphs.

Floyd-Warshall Algorithm for Shortest Path in Weighted Graphs in C

C’s manual memory management and efficient handling of arrays allow for precise control over the algorithm's operation, ensuring you can grasp the inner mechanics of finding shortest paths between all pairs of vertices. 

Unlike higher-level languages, C gives you more flexibility and control, making it ideal for working with such algorithms. In this guide, we’ll walk you through the implementation, step by step.

Step 1: Creating the Graph (Adjacency Matrix)

The first step is setting up the graph as an adjacency matrix, where each cell in the matrix represents the distance between two vertices. If there's no direct edge between two vertices, the distance is set to infinity (∞).

Here’s how to define the graph structure in C:

#define INF 99999  // A large value representing infinity
void initializeGraph(int graph[][4]) {
    graph[0][0] = 0;  graph[0][1] = 4;  graph[0][2] = INF; graph[0][3] = 5;
    graph[1][0] = INF; graph[1][1] = 0;  graph[1][2] = 1;  graph[1][3] = INF;
    graph[2][0] = 2;  graph[2][1] = INF; graph[2][2] = 0;  graph[2][3] = 3;
    graph[3][0] = INF; graph[3][1] = INF; graph[3][2] = 1;  graph[3][3] = 0;
}

In the above code, the graph[][] matrix represents the distances between vertices A, B, C, and D. The matrix will be updated iteratively during the algorithm.

Step 2: Running the Floyd Warshall Algorithm

The next step is to apply the Floyd Warshall Algorithm to compute the shortest paths. The algorithm works by considering each vertex as an intermediate node and updating the shortest path between all pairs of vertices.

Here’s the C code to implement this:

void floydWarshall(int graph[][4]) {
    int V = 4;  // Number of vertices
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // If the path through k is shorter, update the distance
                if (graph[i][j] > graph[i][k] + graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

In this code:

• The outermost loop runs for each intermediate vertex (k).
• The next two loops consider all pairs of vertices (i, j).
• The key part: If the path from i to j through k is shorter than the direct path, we update graph[i][j] with the new shorter value.

Also Read: What are Data Structures & Algorithm

Step 3: Displaying the Resulting Distance Matrix

Once the algorithm has completed, you can display the final matrix, which holds the shortest distances between all pairs of vertices.

Here’s the code to print the matrix:

void printGraph(int graph[][4]) {
    int V = 4;
    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (graph[i][j] == INF) {
                printf("INF ");
            } else {
                printf("%d ", graph[i][j]);
            }
        }
        printf("\n");
    }
}

This will print the shortest path matrix after all iterations. For example, after running the Floyd Warshall Algorithm, the output might look like this:

Shortest distances between every pair of vertices:
0 4 5 5 
3 0 1 4 
2 6 0 3 
3 7 1 0

Complete C Code Example of Floyd Warshall Algorithm

Now, let’s implement the complete program combining all the above steps.

#include <stdio.h>
#define INF 99999
void initializeGraph(int graph[][4]);
void floydWarshall(int graph[][4]);
void printGraph(int graph[][4]);
int main() {
    int graph[4][4];
    initializeGraph(graph);
    floydWarshall(graph);
    printGraph(graph);
    return 0;
}
void initializeGraph(int graph[][4]) {
    graph[0][0] = 0;  graph[0][1] = 4;  graph[0][2] = INF; graph[0][3] = 5;
    graph[1][0] = INF; graph[1][1] = 0;  graph[1][2] = 1;  graph[1][3] = INF;
    graph[2][0] = 2;  graph[2][1] = INF; graph[2][2] = 0;  graph[2][3] = 3;
    graph[3][0] = INF; graph[3][1] = INF; graph[3][2] = 1;  graph[3][3] = 0;
}
void floydWarshall(int graph[][4]) {
    int V = 4;
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (graph[i][j] > graph[i][k] + graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}
void printGraph(int graph[][4]) {
    int V = 4;
    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (graph[i][j] == INF) {
                printf("INF ");
            } else {
                printf("%d ", graph[i][j]);
            }
        }
        printf("\n");
    }
}

Code Explanation:

• Step 1: The graph is initialized with the direct distances between vertices, with infinity (∞) representing no direct edge.
• Step 2: The Floyd Warshall Algorithm updates the graph matrix by considering each vertex as an intermediate node.
• Step 3: The final distance matrix is printed, showing the shortest paths between every pair of vertices.

Output:

Input Graph (initial distances):

  A   B   C   D
A   0   4   ∞   5
B   ∞   0   1   ∞
C   2   ∞   0   3
D   ∞   ∞   1   0

• A to B = 4 (direct distance)
• B to C = 1 (direct distance)
• C to D = 3 (direct distance)
• A to C = ∞ (no direct path, initially)

After running the Floyd Warshall Algorithm, the updated distance matrix will be:

Shortest distances between every pair of vertices:
0 4 5 5 
3 0 1 4 
2 6 0 3 
3 7 1 0 

• A to A = 0 (distance to itself).
• A to B = 4 (direct distance).
• A to C = 5 (shortest path via B: A → B → C).
• A to D = 5 (direct distance).
• B to A = 3 (via C: B → C → A).
• B to B = 0 (distance to itself).
• B to C = 1 (direct distance).
• B to D = 4 (via C: B → C → D).
• C to A = 2 (direct distance).
• C to B = 6 (via D: C → D → B).
• C to C = 0 (distance to itself).
• C to D = 3 (direct distance).
• D to A = 3 (via C: D → C → A).
• D to B = 7 (via C: D → C → B).
• D to C = 1 (direct distance).
• D to D = 0 (distance to itself).

This matrix reflects the shortest paths between all pairs of vertices in the graph after applying the Floyd Warshall Algorithm.

Also Read: 29 C Programming Projects to Try in 2025 With Source Code

Next, let’s now explore how to similarly implement the algorithm in Java. 

How to Implement Floyd-Warshall Algorithm in Java? 

The implementation of the Floyd Warshall Algorithm in Java is similar to C in terms of logic but differs significantly in terms of memory management and syntax. 

Unlike C, where you manually allocate and free memory, Java handles memory automatically with garbage collection, reducing the risk of memory leaks but adding a slight performance overhead. 

Additionally, Java’s higher-level abstractions, like dynamic arrays and built-in error handling, make the code more readable and easier to maintain compared to C’s low-level pointer manipulation. 

While Java offers ease of use and better memory safety, C provides more control over performance and memory management, which might be crucial for large-scale or resource-constrained applications.

Here’s a code implementation of the algorithm using Java:

public class FloydWarshall {
    static final int INF = 99999; // A large value representing infinity
    // Method to initialize the graph with the direct distances between vertices
    public static void initializeGraph(int[][] graph) {
        graph[0][0] = 0;  graph[0][1] = 4;  graph[0][2] = INF; graph[0][3] = 5;
        graph[1][0] = INF; graph[1][1] = 0;  graph[1][2] = 1;  graph[1][3] = INF;
        graph[2][0] = 2;  graph[2][1] = INF; graph[2][2] = 0;  graph[2][3] = 3;
        graph[3][0] = INF; graph[3][1] = INF; graph[3][2] = 1;  graph[3][3] = 0;
    }
    // Method to perform Floyd Warshall algorithm
    public static void floydWarshall(int[][] graph) {
        int V = graph.length; // Number of vertices
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // If the path through vertex k is shorter, update the distance
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }
    // Method to print the shortest distances between all pairs of vertices
    public static void printGraph(int[][] graph) {
        int V = graph.length;
        System.out.println("Shortest distances between every pair of vertices:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (graph[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(graph[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
    // Main method to execute the algorithm
    public static void main(String[] args) {
        int[][] graph = new int[4][4]; // Adjacency matrix for the graph
        // Initialize the graph with direct distances
        initializeGraph(graph);
        // Perform the Floyd Warshall algorithm
        floydWarshall(graph);
        // Print the final shortest path matrix
        printGraph(graph);
    }
}

Explanation:

• initializeGraph(): This method initializes the graph using an adjacency matrix. It represents the direct distances between vertices, with INF indicating no direct path between two vertices.
• floydWarshall(): This is the core of the algorithm. It uses three nested loops to consider every vertex as an intermediate vertex and update the distance matrix accordingly.
• printGraph(): This method prints the final distance matrix, showing the shortest paths between all pairs of vertices. If there's no path (represented by INF), it prints "INF".

Expected Output:

For the given example, the output will be:

Shortest distances between every pair of vertices:
0 4 5 5 
3 0 1 4 
2 6 0 3 
3 7 1 0 

Explanation:

• The matrix displays the shortest distance between each pair of vertices after applying the Floyd Warshall Algorithm.
• INF represents no direct path between two vertices, and the matrix shows the updated shortest paths for all pairs of vertices.

Time Complexity: The time complexity is O(V³) where V is the number of vertices in the graph, as the algorithm has three nested loops over all the vertices.

Space Complexity: The space complexity is O(V²), as we are storing the distance matrix, which is a 2D array of size V × V.

Also Read: Data Structures in Javascript Explained: Importance, Types & Advantages 

Now, let’s dive deeper into how exactly the Floyd-Warshall Algorithm can benefit you as a programmer.

Why Choose the Floyd-Warshall Algorithm? A Comparison of Pros and Cons

The Floyd Warshall Algorithm is a powerful solution for finding the shortest paths between all pairs of vertices in a graph. However, like any algorithm, it has its strengths and weaknesses. Understanding when it’s the right tool for the job and when to look for alternatives can help optimize performance and resource usage.

When to Use the Floyd Warshall Algorithm:

• This algorithm is ideal for applications where you need to find the shortest path between every pair of vertices, such as network routing, logistics, or transportation systems.
• Floyd Warshall is best suited for dense graphs where most vertices are connected, as it processes all pairs of vertices, making it efficient for such scenarios.
• Unlike Dijkstra’s algorithm, which doesn’t work with negative edges, Floyd Warshall can handle graphs with negative weight edges (as long as there are no negative weight cycles).

When Not to Use the Floyd Warshall Algorithm:

• If the graph has very few edges, algorithms like Dijkstra’s or Bellman-Ford might be more efficient, as Floyd Warshall operates at O(V³) time complexity, which can be slower for sparse graphs.
• Since Floyd Warshall uses a 2D matrix to store all pairwise distances, it can become memory-heavy for very large graphs with many vertices.
• For cases where you only need the shortest path from a particular source to all other vertices, Dijkstra’s algorithm or Bellman-Ford is more efficient.

Here’s a comparison of the pros and cons of the Floyd Warshall Algorithm:

So, the Floyd Warshall Algorithm is a robust choice when you need to find the shortest paths between all pairs of vertices in dense graphs. However, its high time complexity and memory usage make it less suitable for sparse graphs or situations where you only need the shortest path from a single source. 

Also Read: Data Structures & Algorithm in Python: Everything You Need to Know 

Now that you understand the algorithm better, it’s time to dive into the real-world applications.

Real World Applications of Floyd-Warshall Algorithm: How It Powers Diverse Industries?

The Floyd Warshall Algorithm is more than just a theoretical concept. It's widely applied in real-world systems where finding the shortest paths between all pairs of vertices is critical. Its ability to handle all-pairs shortest path problems makes it a go-to solution for problems in network routing, logistics, and transportation, among others. 

Let’s dive into some of the unique applications of Floyd-Warshall Algorithm.

1. Network Routing (Optimizing Communication Paths)

In telecommunication networks and internet routing, the Floyd Warshall Algorithm plays a crucial role in ensuring data packets take the most efficient path between any two nodes. By precomputing the shortest paths between all pairs of routers or network nodes, it allows dynamic adjustments to routes when network conditions change. 

For example, if a node or link fails, the algorithm quickly provides the new optimal routing paths, minimizing the delay and ensuring high availability. This is especially beneficial in data centers or cloud networks that require constant, real-time optimizations.

2. Logistics and Transportation (Route Optimization)

The Floyd Warshall Algorithm is widely used in logistics and transportation management systems. Consider a delivery company that needs to determine the shortest route between multiple cities. By applying the algorithm, the system can calculate the shortest path between all cities, optimizing fuel consumption, time, and resources. 

This is particularly important in large transportation networks where companies need to reduce costs and improve delivery times. The algorithm’s ability to efficiently compute paths between all locations ensures that transportation systems are running optimally at all times.

3. GPS Navigation Systems (Dynamic Pathfinding)

In GPS navigation systems, the Floyd Warshall Algorithm is crucial for route planning, especially in complex cities with multiple routes, intersections, and roads. It helps the system precompute and store the shortest distances between all intersections. 

Whenever a user inputs a destination, the system can quickly find the shortest route by referencing the precomputed matrix of distances. This algorithm also helps in real-time rerouting—if a road is blocked or under construction, the system can find alternative paths efficiently by utilizing the updated shortest path matrix.

4. Public Transportation (Efficient Transit Mapping)

Cities with public transportation systems use the Floyd Warshall Algorithm to create optimal route maps for buses, trains, and metros. The algorithm can calculate the shortest travel times between various stations. This helps transit agencies optimize schedules, reduce wait times, and improve service reliability. 

Updating the system with real-time data on delays or route changes ensures that passengers have the quickest possible connections at any time. This is particularly important for urban areas with complex transit networks.

5. Urban Planning and Traffic Management (Optimizing City Traffic Flow)

Urban planners and traffic management systems use the Floyd Warshall Algorithm to manage and optimize city traffic flow. By analyzing the shortest paths between all key intersections, the algorithm helps city planners design more efficient road networks, improving both vehicular movement and pedestrian pathways. 

It can also help in simulating traffic scenarios and finding the quickest routes during peak hours, events, or emergencies. For instance, if traffic congestion occurs, the system can reroute vehicles in real-time to avoid delays.

6. Game Development (Character and Pathfinding Algorithms)

In game development, especially for role-playing or strategy games, the Floyd Warshall Algorithm is used to optimize character movement and AI pathfinding. For games with large maps, it helps precompute the shortest paths between all locations. This allows NPCs (non-player characters) to move efficiently and respond intelligently to player actions. 

Instead of recalculating paths in real-time, the algorithm allows the game to access precomputed paths, saving valuable processing time and providing smooth gameplay, especially in open-world games with numerous destinations.

7. Social Networks (Optimizing Connections and Recommendations)

The Floyd Warshall Algorithm can be applied in social networking platforms to find the shortest paths between users, which is crucial for recommending friends or connections. It helps platforms identify the shortest "degrees of separation" between users, making it possible to suggest people who may have mutual connections. 

This application is also beneficial for recommending groups, content, or events based on a user's connections within the network, improving user engagement and interaction.

8. Supply Chain Management (Optimizing Delivery Routes and Storage)

Supply chain management systems benefit from the Floyd Warshall Algorithm by precomputing the shortest delivery routes between suppliers, warehouses, and retailers. By calculating the shortest possible paths for shipments, the system can help reduce delivery costs and times. 

Additionally, it helps in warehouse management by optimizing the routes for storing and retrieving items, reducing the time spent searching for goods, and enhancing overall operational efficiency.

9. Airline Scheduling (Minimizing Delays and Connections)

Airlines use the Floyd Warshall Algorithm to compute the shortest paths between all airports in their network. This helps in planning efficient flight schedules, minimizing layovers, and reducing delays between connecting flights. 

The algorithm can also help airlines reroute planes if a delay occurs at one airport, ensuring that passengers reach their destinations as quickly as possible. By keeping the network of flights optimized, airlines can improve customer satisfaction and operational efficiency.

By leveraging the algorithm’s ability to handle all-pairs shortest paths, industries can streamline operations, reduce costs, and enhance user experience in diverse domains.

Also Read: 20 Most Popular Programming Languages in 2025

Now that you’re familiar with the applications of Floyd-Warshall Algorithm, let’s explore how upGrad can take your learning journey forward.

How upGrad Can Enhance Your Understanding of Advanced Programming Concepts?

Now that you’ve strengthened your grasp of the Floyd Warshall Algorithm, it’s the perfect time to improve your advanced programming skills. upGrad’s expert-led courses focus on complex algorithms and data structures. They will give you the practical expertise to apply these concepts to real-world problems.

Through hands-on projects, you’ll apply the Floyd Warshall Algorithm to solve complex problems and build high-performance applications.

Here are some relevant courses you can explore:

• Java Object-oriented Programming
• JavaScript Basics from Scratch
• Master of Science in AI and Data Science
• Best Full Stack Developer Bootcamp 
• Master of Design in User Experience

If you're unsure about the next step in your learning journey, you can contact upGrad’s personalized career counseling for guidance on choosing the best path tailored to your goals. You can also visit your nearest upGrad center and start hands-on training today!

Expand your expertise with the best resources available. Browse the programs below to find your ideal fit in Best Machine Learning and AI Courses Online.

Best Machine Learning and AI Courses Online

Discover in-demand Machine Learning skills to expand your expertise. Explore the programs below to find the perfect fit for your goals.

In-demand Machine Learning Skills

Discover popular AI and ML blogs and free courses to deepen your expertise. Explore the programs below to find your perfect fit.

Popular AI and ML Blogs & Free Courses