Floyd-Warshall Algorithm
Graph Selection
Playback Controls
Select start and target nodes to begin
Floyd-Warshall Info
Key Features:
- • Finds all-pairs shortest paths
- • Uses dynamic programming
- • Time complexity: O(V³)
- • Handles negative weights
- • Detects negative cycles
Legend:
Reference implementation of Floyd-Warshall Algorithm. Select a language tab to view and copy the code.
#define INF 99999
#define V 4
void floyd_warshall(int dist[V][V]) {
/* dist[][] already initialised as the adjacency matrix */
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}#include <vector>
#include <algorithm>
#include <limits>
void floydWarshall(std::vector<std::vector<int>>& dist) {
int n = static_cast<int>(dist.size());
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
// Negative-cycle detection: dist[i][i] < 0
for (int i = 0; i < n; i++)
if (dist[i][i] < 0)
throw std::runtime_error("Negative cycle detected");
}public static void floydWarshall(int[][] dist) {
int n = dist.length;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] != Integer.MAX_VALUE / 2
&& dist[k][j] != Integer.MAX_VALUE / 2
&& dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
// Negative-cycle check
for (int i = 0; i < n; i++)
if (dist[i][i] < 0)
throw new IllegalStateException("Negative cycle detected");
}def floyd_warshall(dist: list[list[float]]) -> None:
n = len(dist)
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
# Detect negative-weight cycles
for i in range(n):
if dist[i][i] < 0:
raise ValueError(f"Negative cycle through node {i}")function floydWarshall(dist) {
const n = dist.length;
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (dist[i][k] + dist[j][k] < dist[i][j]) // via k
dist[i][j] = dist[i][k] + dist[k][j];
// Negative-cycle check: dist[i][i] < 0
for (let i = 0; i < n; i++)
if (dist[i][i] < 0) throw new Error("Negative cycle detected");
}Python — Code Walkthrough
float("inf") — safe with addition
dist: list[list[float]]Using float("inf") for missing edges means dist[i][k] + dist[k][j] is float("inf") when either operand is inf — no overflow or guard needed. Python float arithmetic handles inf correctly.
Three nested range loops
for k in range(n): for i in range(n): for j in range(n):The k loop (intermediate vertex) must be outermost. If i or j were outermost, we would use future-state dist values before they are fully computed.
f-string in error message
raise ValueError(f"Negative cycle through node {i}")The f-string includes which node triggered the negative cycle, providing actionable information. Useful for debugging graph inputs.
In-place modification — None return
) -> NoneThe function modifies the passed matrix directly and returns None. The caller reads results from dist[][] after the function returns.