Floyd-Warshall Algorithm

@floydwarshall_algorithm

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes by gradually improving paths using intermediate nodes.

Pseudo-code
function floyd_warshall(d):

  # Step 1: Try every node as an intermediate
  for k from 0 to n-1:

    # Step 2: Check all pairs (i, j)
    for i from 0 to n-1:
      for j from 0 to n-1:

        # Step 3: Relax using node k
        if d[i][k] + d[k][j] < d[i][j]:
          d[i][j] = d[i][k] + d[k][j]

  return d
  • d A distance matrix where d[i][j] stores the shortest distance from node i to node j.
  • i Starting node of a path.
  • j Ending node of a path.
  • k Intermediate node we try to use to improve the path from i to j.
  • INF A very large value representing infinity, used when no direct path exists.
Recipe Steps
1

Start with a table — Imagine a table where you write the distance between every pair of cities.

2

Pick a middle city — Ask: 'Can going through this city make any route shorter?'

3

For every pair of cities (A to B), check if A → middle → B is shorter than the current path.

4

If yes, update the distance in the table.

5

Repeat this for every possible middle city until no improvements can be made.

Questions & Answers

Try all possible intermediate nodes to improve shortest paths.

The shortest distance from node i to node j.

Yes, but not negative cycles.

We compare d[i][j] with d[i][k] + d[k][j].
- Time complexity is O(n^3), so it is slow for large graphs.
- Works well when you need all-pairs shortest paths.
- Tip: Think of it as gradually improving a full distance table.
- Common mistake: Forgetting to initialize d[i][i] = 0.
- If d[i][i] becomes negative, it means there is a negative cycle.

Related Algorithms
Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest path from a source node to all other nodes, even when there are negative edge weights. It works by repeatedly improving distance estimates.

View
Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from one starting node to all other nodes in a graph by always expanding the currently closest node first.

View
Dinic's Algorithm

Dinic's Algorithm finds the maximum flow in a network by building layers using BFS and then sending flow using DFS in these layers, making it faster than simpler methods.

View