Matrix Based
Unlike Dijkstra, which uses a priority queue, Floyd-Warshall uses a 2D matrix to store the shortest distance between every pair (i, j).
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
The Floyd-Warshall algorithm computes shortest paths between all pairs of vertices in a weighted graph. It works by considering every node as a potential intermediate point.
Unlike Dijkstra, which uses a priority queue, Floyd-Warshall uses a 2D matrix to store the shortest distance between every pair (i, j).
For every pair (i, j), we check if going through intermediate node 'k' gives a shorter path: dist[i][j] > dist[i][k] + dist[k][j].
It can handle negative weights, but not negative cycles. It can however be used to detect negative cycles if dist[i][i] < 0.
Ideal for dense graphs or when you need a distance table for all possible connections in a network.