Floyd-Warshall Algorithm

Say you have a map of cities with roads between them. Now someone asks you a question. What is the shortest distance from every city to every other city? Not just from one starting point. All of them, at once. Dijkstra gives you shortest paths from one source. You could run it again and again for every city. But that gets fiddly fast. It gets even harder when some roads have negative weights. The Floyd-Warshall algorithm solves this whole thing in one clean shot. So let us see how it works.

🗺️ A Real-World Way to Picture It

Imagine a small group of friends. They want the cheapest flight cost between every pair of cities they live in. Riya is in Delhi. Arjun is in Mumbai. Alex is in Chennai.

There is a direct flight between some cities. But sometimes flying through a third city is cheaper. Delhi to Chennai direct might cost a lot. Yet Delhi to Mumbai, then Mumbai to Chennai, can cost less together.

So the real question for every pair is simple. Can we make the trip cheaper by stopping at some city in the middle? That single question is the whole heart of Floyd-Warshall. We keep asking it for every possible middle city.

🎯 What It Actually Does

Floyd-Warshall finds the shortest path between every pair of vertices in a weighted graph. We call this the all-pairs shortest path problem. That just means the shortest distance from each node to each other node.

Here is the core idea in plain words.

• We keep a grid of distances. The cell at row i, column j holds the current best known distance from vertex i to vertex j.
• We pick one vertex at a time and call it the intermediate vertex, written as k. An intermediate vertex is a city we are allowed to stop at on the way.
• For every pair i and j, we ask one thing. Is going from i to k and then k to j shorter than what we already have?
• If yes, we update the cell with the shorter distance.

That is it. We do this for every choice of k. Once we have tried every vertex as a middle stop, every cell holds the true shortest distance.

🧮 The Distance Matrix

Let us use a small graph with four vertices: 0, 1, 2, 3. The arrows show directed edges and their weights.

We start by writing down what we already know. The distance from a vertex to itself is 0. If there is a direct edge, we use its weight. If there is no direct edge, we treat it as infinity. That just means “no known path yet”.

This starting grid is the distance matrix. Here INF stands for infinity.

Now watch one update. Look at the path from 0 to 2. Right now it says INF, because there is no direct edge. But 0 can reach 1 with cost 3. And 1 can reach 2 with cost -2. So through vertex 1, the cost is 3 + (-2) = 1. That beats INF. So we write 1 into the cell for 0 to 2. This is exactly what the algorithm does, again and again, for every middle vertex.

🪜 Steps to Run Floyd-Warshall

Here is the plan before we write any code.

1. Build the distance matrix. Put 0 on the diagonal, edge weights where edges exist, and a large value (our INF) everywhere else.
2. Take the first vertex as the intermediate vertex k.
3. For every pair of vertices i and j, check if dist[i][k] + dist[k][j] is smaller than dist[i][j].
4. If it is smaller, update dist[i][j] with that smaller value.
5. Repeat steps 2 to 4 for every vertex as k.
6. When all vertices have been used as k, the matrix holds every shortest distance.

So it is three nested loops. The outer one runs over k, then i, then j.

💻 The Code

Now let us put those steps into code. We build the matrix, run the three loops, then print the all-pairs distances. We use a big number for infinity. We print INF for any pair that still cannot be reached.

#include <stdio.h>

#define V 4
#define INF 99999

// Run Floyd-Warshall on the distance matrix in place.
void floydWarshall(int dist[V][V]) {
    // k is the intermediate vertex (the middle stop).
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // Is going through k cheaper than what we have?
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

void printMatrix(int dist[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] >= INF) printf("INF ");
            else printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int dist[V][V] = {
        {0, 3, INF, 8},
        {INF, 0, -2, INF},
        {INF, INF, 0, 2},
        {1, INF, INF, 0}
    };
    floydWarshall(dist);
    printMatrix(dist);
    return 0;
}

0 3 1 3
1 0 -2 0
3 6 0 2
1 4 2 0

#include <iostream>
using namespace std;

const int V = 4;
const int INF = 99999;

// Run Floyd-Warshall on the distance matrix in place.
void floydWarshall(int dist[V][V]) {
    // k is the intermediate vertex (the middle stop).
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // Is going through k cheaper than what we have?
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

void printMatrix(int dist[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] >= INF) cout << "INF ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
}

int main() {
    int dist[V][V] = {
        {0, 3, INF, 8},
        {INF, 0, -2, INF},
        {INF, INF, 0, 2},
        {1, INF, INF, 0}
    };
    floydWarshall(dist);
    printMatrix(dist);
    return 0;
}

0 3 1 3
1 0 -2 0
3 6 0 2
1 4 2 0

public class FloydWarshall {
    static final int V = 4;
    static final int INF = 99999;

    // Run Floyd-Warshall on the distance matrix in place.
    static void floydWarshall(int[][] dist) {
        // k is the intermediate vertex (the middle stop).
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // Is going through k cheaper than what we have?
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }

    static void printMatrix(int[][] dist) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] >= INF) System.out.print("INF ");
                else System.out.print(dist[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] dist = {
            {0, 3, INF, 8},
            {INF, 0, -2, INF},
            {INF, INF, 0, 2},
            {1, INF, INF, 0}
        };
        floydWarshall(dist);
        printMatrix(dist);
    }
}

0 3 1 3
1 0 -2 0
3 6 0 2
1 4 2 0

INF = 99999

# Run Floyd-Warshall on the distance matrix and return it.
def floyd_warshall(dist):
    n = len(dist)
    # k is the intermediate vertex (the middle stop).
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # Is going through k cheaper than what we have?
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

def print_matrix(dist):
    for row in dist:
        print(" ".join("INF" if v >= INF else str(v) for v in row))

graph = [
    [0, 3, INF, 8],
    [INF, 0, -2, INF],
    [INF, INF, 0, 2],
    [1, INF, INF, 0],
]

print_matrix(floyd_warshall(graph))

0 3 1 3
1 0 -2 0
3 6 0 2
1 4 2 0

const INF = 99999;

// Run Floyd-Warshall on the distance matrix and return it.
function floydWarshall(dist) {
  const n = dist.length;
  // k is the intermediate vertex (the middle stop).
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        // Is going through k cheaper than what we have?
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

function printMatrix(dist) {
  for (const row of dist) {
    console.log(row.map((v) => (v >= INF ? "INF" : v)).join(" "));
  }
}

const graph = [
  [0, 3, INF, 8],
  [INF, 0, -2, INF],
  [INF, INF, 0, 2],
  [1, INF, INF, 0],
];

printMatrix(floydWarshall(graph));

0 3 1 3
1 0 -2 0
3 6 0 2
1 4 2 0

Read the output as a grid. The cell at row 1, column 2 shows -2. That is the shortest path from vertex 1 to vertex 2. The cell at row 0, column 2 shows 1. That is the 3 + (-2) path through vertex 1 we worked out by hand earlier. It matches.

⏱️ How Fast Is It?

So the running time depends only on the number of vertices, not on how many edges there are. That makes it a great fit for dense graphs. A dense graph is one where almost every pair of vertices has an edge. For a graph with very few edges, running Dijkstra from each vertex can be faster.

Here is how it compares with the other shortest-path tools.

➖ What About Negative Edges?

A nice thing about Floyd-Warshall is that it handles negative edge weights just fine. A negative edge weight is a road whose cost is less than zero, like a discount. You saw one in our graph. The edge from 1 to 2 had weight -2, and the algorithm used it correctly.

But there is one thing it cannot handle. That is a negative cycle. A negative cycle is a loop in the graph whose total weight is less than zero. If such a loop exists, you could keep going around it forever and the path cost would keep dropping. So there is no real shortest path at all.

⚠️ Common Mistakes

A few slips trip people up the first time.

• Putting k as an inner loop instead of the outer loop. The intermediate vertex must be the outermost loop, or the results come out wrong.
• Using a real “infinity” value that overflows when you add two together. With a giant INF, INF + INF can wrap around to a negative number in C or Java. Pick a large but safe value like 99999, or skip the update when either side is already INF.
• Forgetting the diagonal starts at 0. The distance from a vertex to itself is zero, not infinity.
• Assuming it works with negative cycles. It does not. Check the diagonal afterward if negative cycles are possible.

🧩 What You’ve Learned

✅ Floyd-Warshall finds the shortest path between every pair of vertices, the all-pairs shortest path problem.

✅ The core idea is one question repeated. For each intermediate vertex k, can going through k shorten the path between i and j?

✅ It is three nested loops over a distance matrix, with k as the outer loop.

✅ It runs in O(V³) time and O(V²) space, which suits dense graphs well.

✅ It handles negative edge weights, but not negative cycles, which you can detect by checking the diagonal.

🚀 What’s Next?

• Bellman-Ford Algorithm
• Dijkstra Shortest Path Algorithm