Floyd Warshall vs. Multi-Source Dijkstra | Two Ways to Solve All-Pairs Shortest Paths

Master Floyd Warshall for APSP and see when a Dijkstra-per-source loop beats it. Clear intuition, Python code, and complexity breakdown.

Here’s the [Problem Link] to begin with.

1. Problem in one line

Given an n × n weighted graph matrix dist, replace each dist[i][j] with the weight of the shortest path from vertex i to vertex j. 10**8 stands for “∞”.

2. Why two algorithms?

We will implement both and compare.

3. Intuition & approach

3.1 Floyd Warshall (dynamic programming)

1. Consider every vertex via as a possible intermediate stop.
2. For each pair (i, j) test whether going i → via → j is cheaper than the best path already known.
3. Repeat for all via ∈ [0, n-1]. After n rounds, every indirect shortcut is tried.

This is classic DP on triples – indices mean “shortest path that only uses
vertices ≤ via as intermediates”.

3.2 Dijkstra run n times

1. Convert the matrix to an adjacency list — skip ∞ entries.
2. For each source src run standard min-heap Dijkstra to fill row src.
3. Copy the row back into the matrix.

Total complexity scales with n times the cost of one Dijkstra.

4. Python code

4.1 Floyd Warshall

class Solution:
    def floydWarshall(self, dist):
        n = len(dist)
        INF = 10**8

        for via in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][via] != INF and dist[via][j] != INF:
                        dist[i][j] = min(dist[i][j],
                                         dist[i][via] + dist[via][j])
        return dist

4.2 Multi-Source Dijkstra

import heapq

class Solution:
    INF = 10**8

    def floydWarshall(self, dist):
        """Fill dist with shortest-path weights using Dijkstra per source."""

        n = len(dist)

        # 1) build adjacency list once
        adj = [[] for _ in range(n)]
        for u in range(n):
            for v, w in enumerate(dist[u]):
                if u != v and w != self.INF:      # ignore self & no-edge
                    adj[u].append((v, w))

        # 2) run Dijkstra from every vertex
        for src in range(n):
            best = [self.INF] * n
            best[src] = 0
            pq = [(0, src)]

            while pq:
                d, u = heapq.heappop(pq)
                if d != best[u]:          # stale heap entry
                    continue
                for v, w in adj[u]:
                    nd = d + w
                    if nd < best[v]:
                        best[v] = nd
                        heapq.heappush(pq, (nd, v))

            dist[src][:] = best           # update the matrix row

        return dist

5. Complexity comparison

Rule of thumb

• Dense or negative edges? → Floyd Warshall.
• Sparse with non-negative weights and n ≳ 500? → Dijkstra per source.

6. Dry-run snippet (3-node graph)

dist = [
  [0,     4, 11],
  [10,    0,  2],
  [5,   INF,  0]
]

Floyd Warshall finds path 0→1→2 = 6 replaces 11,
and 2→0→1 = 9 beats INF.
Final matrix:

0 4 6
7 0 2
5 9 0

Dijkstra loop yields the same matrix (because all weights ≥ 0).

7. Conclusion

The focus word Floyd Warshall stands for the all-pairs classic:

• O(n³), supports negative weights, trivially in-place.
• Dijkstra-per-source trades that for speed on larger, positive-weight, sparse graphs.

Pick the one that matches your graph’s density and edge sign, and keep both techniques handy for interviews and contests.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.