what approach is being followed in floyd warshall algorithm?
The Floyd–Warshall algorithm follows the dynamic programming approach to solve the all‑pairs shortest path problem.
Core idea in one line
It builds shortest paths incrementally , by repeatedly improving a distance matrix using every vertex as a possible intermediate node, which is exactly the dynamic programming “optimal substructure + overlapping subproblems” style.
Quick Scoop ✅
- Approach type: Dynamic programming.
- Problem type: All‑pairs shortest paths in a weighted graph (can handle negative edges, but not negative cycles).
- Key principle: Optimal substructure – if the shortest path from iii to jjj goes through kkk, then the path i→ki\to ki→k and k→jk\to jk→j are themselves shortest paths.
- How it works conceptually:
- Start with a matrix of direct edge distances (or ∞ if no edge).
- For each vertex kkk, try to “relax” all pairs (i,j)(i,j)(i,j) via kkk:
- dist[i][j]=min(dist[i][j],textdist[i][k]+dist[k][j])\text{dist}[i][j]=\min(\text{dist}[i][j],\\text{dist}[i][k]+\text{dist}[k][j])dist[i][j]=min(dist[i][j],textdist[i][k]+dist[k][j]).
* After considering all kkk, the matrix holds the shortest distances between all pairs.
Mini sections
1. Why it’s dynamic programming
Floyd–Warshall defines subproblems as:
- “Shortest path from node iii to node jjj using only the first kkk vertices as intermediates.”
Then it builds answers in stages:
- For k=0k=0k=0: only direct edges are allowed.
- For k=1k=1k=1: allow paths that may pass through vertex 1.
- For k=2k=2k=2: allow vertices 1 and 2 as intermediates, and so on until all vertices are allowed.
This layered construction and reuse of previous results is the hallmark of dynamic programming.
2. Contrast with other approaches
Here’s a quick comparison so the “approach” angle is clearer:
| Algorithm | Approach type | Typical use |
|---|---|---|
| Floyd–Warshall | Dynamic programming | [10][3][9]All‑pairs shortest paths, dense graphs, can handle negative edges (no negative cycles). | [1][3][9]
| Dijkstra | Greedy algorithm | [5][10]Single‑source shortest paths with non‑negative weights. | [5][10]
3. Tiny story‑style example
Imagine you have 3 cities: A, B, C. You know direct distances A→B, B→C, A→C.
You first write them in a table. Then you ask, “If I allow going through B,
can A reach C cheaper via A→B→C than directly A→C?” You update the table if
yes.
Then you repeat the same thought for each city as a possible middle stop. This
repeated “check via k and update” is exactly how the algorithm dynamically
builds the optimal answers.
4. Key takeaway
So, to answer your question directly:
The Floyd–Warshall algorithm follows a dynamic programming approach, using intermediate vertices step by step to compute all‑pairs shortest paths.
TL;DR:
Floyd–Warshall = all‑pairs shortest paths + dynamic programming on a distance
matrix, updating it by trying every node as an intermediate.
Information gathered from public forums or data available on the internet and portrayed here.
