Floyd Warshall in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#define INF 9999
int main() {
    int g[3][3] = {{0, 4, INF}, {INF, 0, 5}, {1, INF, 0}};
    for (int k = 0; k < 3; k++)
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (g[i][k] + g[k][j] < g[i][j])
                    g[i][j] = g[i][k] + g[k][j];
    for (int i = 0; i < 3; i++, puts(""))
        for (int j = 0; j < 3; j++)
            printf("%4d ", g[i][j]);
}

C Output

Input:

Graph =

0 → 1 (4)

1 → 2 (5)

2 → 0 (1)
Output:

Input: 3x3 matrix

Output:  
   0    4    9  
   6    0    5  
   1    5    0

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main() {
    int INF = 1e9;
    vector<vector<int>> g = {{0, 3, INF}, {INF, 0, 1}, {2, INF, 0}};
    for (int k = 0; k < 3; k++)
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    for (auto& r : g) {
        for (int d : r) cout << setw(4) << d << " ";
        cout << "\n";
    }
}

C++ Output

Input:

0→1(3), 1→2(1), 2→0(2)
Output:

Input: 3x3 adjacency matrix

Output:  
  0   3   4  
  3   0   1  
  2   5   0

JAVA Program

import java.util.*;
class Main {
    public static void main(String[] args) {
        int INF = 99999;
        int[][] g = {{0, INF, 8}, {1, 0, INF}, {INF, 2, 0}};
        for (int k = 0; k < 3; k++)
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    if (g[i][k] + g[k][j] < g[i][j])
                        g[i][j] = g[i][k] + g[k][j];
        for (int[] r : g) {
            for (int d : r) System.out.printf("%4d ", d);
            System.out.println();
        }
    }
}

JAVA Output

Input:

0→2(8), 1→0(1), 2→1(2)
Output:

Input: 3x3 matrix

Output:  
  0  10   8  
  1   0   9  
  3   2   0

Python Program

INF = 99999
g = [[0, 7, INF], [3, 0, 1], [INF, INF, 0]]
for k in range(3):
    for i in range(3):
        for j in range(3):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])
for row in g:
    print(" ".join(f"{x:4}" for x in row))

Python Output

Input:
0→1(7), 1→0(3), 1→2(1)
Output:
Input: 3x3 adjacency matrix

Output: 

   0    7    8  
   3    0    1  
99999 99999   0

In-Depth Explanation

Example

Let’s take the C++ example.

The graph is:

0 → 1 (3)

1 → 2 (1)

2 → 0 (2)

Initially, the shortest path from 0 to 2 is infinity. But through Floyd Warshall:

0→1 (3)

1→2 (1)

= 0→2 becomes 4

Also:

2→0 (2)

0→1 (3)

= 2→1 becomes 5

The final shortest paths reflect all possible minimal connections between every pair.

Real-Life Analogy

Imagine you’re planning travel between cities where some roads are unavailable or have high tolls.

Floyd Warshall assists you in calculating the most economical travel plan from each city to each other city, even without a direct road — by setting up available paths and minimizing total cost of travel.

It's akin to comparing all your choices, even through stops or transfers, and selecting the best route between each two points.

Why It Matters

Floyd Warshall is the industry benchmark for resolving the All-Pairs Shortest Path (APSP) issue.

Unlike Dijkstra (which does one source to work from), this one calculates distances between every node in O(n^3) time — elegant and effective.

It's ideal when:

You preprocess travel costs among all points

You need to verify shortest connections between any two

Weights are non-negative and the graph is dense

Learning Insights

With this algorithm, you achieve:

Triple nested loops with beautiful logic

Dynamic programming for graphs

Matrix-based graph representation

Concepts such as transitive closure, reachability, and multi-source path planning

It further provides understanding of optimization between nodes, and how changing a single edge can affect numerous shortest paths.

Interview & Real-World Use

This algorithm is regularly asked in:

Graph theory problems

Dynamic path planning

Applications with complete matrix representation of connectivity

Used in:

Routing tables in networks

Public transport planners

Game AI pathfinding for global maps

Traffic management systems

Database query optimization where join paths are significant

The Floyd Warshall Algorithm is perhaps the most beautiful and influential algorithms in graph theory, all-pairs shortest path computation in an organized and efficient manner. It is particularly useful when working with dense graphs or where each node may have to link to each other node efficiently. Whether you're designing logistics, route optimization, a smart GPS, or a tough coding interview problem, Floyd Warshall gives you the dynamic programming tools and intuition necessary to calculate shortest paths with ease. The sample code in C, C++, Java, and Python makes it easy to implement, while the detailed explanation makes it easier to appreciate why and how it does what it does.