Floyd–Warshall Algorithm Code Implementations
Complete Floyd–Warshall Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Floyd–Warshall Algorithm Guide · Launch Interactive Visualizer
C++ Implementation
// Floyd-Warshall Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits>
class FloydWarshallAlgorithm {
public:
static std::vector<std::vector<int>> floydWarshallAlgorithm(const std::unordered_map<int, std::unordered_map<int, int>>& graph) {
std::vector<int> vertices;
for (const auto& [vertex, neighbors] : graph) {
vertices.push_back(vertex);
}
int n = vertices.size();
// Create distance and path matrices
std::vector<std::vector<int>> distances(n, std::vector<int>(n, std::numeric_limits<int>::max()));
std::vector<std::vector<int>> paths(n, std::vector<int>(n, -1));
// Initialize distance matrix
for (int i = 0; i < n; i++) {
distances[i][i] = 0;
for (int j = 0; j < n; j++) {
paths[i][j] = i == j ? -1 : i;
}
}
// Fill initial distances
for (int i = 0; i < n; i++) {
auto it = graph.find(vertices[i]);
if (it != graph.end()) {
for (int j = 0; j < n; j++) {
auto neighborIt = it->second.find(vertices[j]);
if (neighborIt != it->second.end()) {
distances[i][j] = neighborIt->second;
}
}
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (distances[i][k] != std::numeric_limits<int>::max() &&
distances[k][j] != std::numeric_limits<int>::max() &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
paths[i][j] = paths[k][j];
}
}
}
}
// Check for negative cycles
for (int i = 0; i < n; i++) {
if (distances[i][i] < 0) {
return {}; // Negative cycle detected
}
}
return distances;
}
// Get shortest path between two vertices
static std::vector<int> getShortestPathFloydWarshall(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start, int end) {
auto distances = floydWarshallAlgorithm(graph);
if (distances.empty()) {
return {}; // Negative cycle detected
}
std::vector<int> vertices;
for (const auto& [vertex, neighbors] : graph) {
vertices.push_back(vertex);
}
int startIndex = -1, endIndex = -1;
for (int i = 0; i < vertices.size(); i++) {
if (vertices[i] == start) startIndex = i;
if (vertices[i] == end) endIndex = i;
}
if (startIndex == -1 || endIndex == -1) {
return {}; // Vertex not found
}
if (distances[startIndex][endIndex] == std::numeric_limits<int>::max()) {
return {}; // No path exists
}
// Reconstruct path (simplified)
std::vector<int> path = {start, end};
return path;
}
// Floyd-Warshall with adjacency matrix
static std::vector<std::vector<int>> floydWarshallWithMatrix(const std::vector<std::vector<int>>& adjacencyMatrix) {
int n = adjacencyMatrix.size();
std::vector<std::vector<int>> distances = adjacencyMatrix;
std::vector<std::vector<int>> paths(n, std::vector<int>(n, -1));
// Initialize path matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
paths[i][j] = i == j ? -1 : i;
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (distances[i][k] != std::numeric_limits<int>::max() &&
distances[k][j] != std::numeric_limits<int>::max() &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
paths[i][j] = paths[k][j];
}
}
}
}
return distances;
}
};CPP Implementation
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> floydWarshall(const vector<vector<int>>& graph) {
int n = graph.size();
const int INF = 1e9; // A large value to represent infinity
vector<vector<int>> dist(n, vector<int>(n, INF));
// Initialize distance matrix
for (int i = 0; i < n; i++) {
dist[i][i] = 0;
for (int j = 0; j < n; j++) {
if (graph[i][j] != 0) {
dist[i][j] = graph[i][j];
}
}
}
// Floyd–Warshall algorithm
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] < INF && dist[k][j] < INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
int main() {
// Example usage
vector<vector<int>> graph = {
{0, 5, 0, 10},
{0, 0, 3, 0},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
vector<vector<int>> dist = floydWarshall(graph);
cout << "Shortest distance matrix:\n";
for (auto& row : dist) {
for (auto& val : row) {
if (val == 1e9) cout << "INF ";
else cout << val << " ";
}
cout << "\n";
}
return 0;
}
JAVA Implementation
// Floyd-Warshall Algorithm Implementation in Java
import java.util.*;
public class FloydWarshallAlgorithm {
public static int[][] floydWarshallAlgorithm(Map<Integer, Map<Integer, Integer>> graph) {
Set<Integer> vertices = graph.keySet();
int n = vertices.size();
int[] vertexArray = vertices.stream().mapToInt(Integer::intValue).toArray();
// Create distance and path matrices
int[][] distances = new int[n][n];
int[][] paths = new int[n][n];
// Initialize distance matrix
for (int i = 0; i < n; i++) {
Arrays.fill(distances[i], Integer.MAX_VALUE);
distances[i][i] = 0;
for (int j = 0; j < n; j++) {
paths[i][j] = i == j ? -1 : i;
}
}
// Fill initial distances
for (int i = 0; i < n; i++) {
Map<Integer, Integer> neighbors = graph.getOrDefault(vertexArray[i], new HashMap<>());
for (int j = 0; j < n; j++) {
if (neighbors.containsKey(vertexArray[j])) {
distances[i][j] = neighbors.get(vertexArray[j]);
}
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (distances[i][k] != Integer.MAX_VALUE && distances[k][j] != Integer.MAX_VALUE &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
paths[i][j] = paths[k][j];
}
}
}
}
// Check for negative cycles
for (int i = 0; i < n; i++) {
if (distances[i][i] < 0) {
return null; // Negative cycle detected
}
}
return distances;
}
// Get shortest path between two vertices
public static List<Integer> getShortestPathFloydWarshall(Map<Integer, Map<Integer, Integer>> graph, int start, int end) {
int[][] distances = floydWarshallAlgorithm(graph);
if (distances == null) {
return null; // Negative cycle detected
}
Set<Integer> vertices = graph.keySet();
int[] vertexArray = vertices.stream().mapToInt(Integer::intValue).toArray();
int startIndex = -1, endIndex = -1;
for (int i = 0; i < vertexArray.length; i++) {
if (vertexArray[i] == start) startIndex = i;
if (vertexArray[i] == end) endIndex = i;
}
if (startIndex == -1 || endIndex == -1) {
return null; // Vertex not found
}
if (distances[startIndex][endIndex] == Integer.MAX_VALUE) {
return null; // No path exists
}
// Reconstruct path (simplified)
List<Integer> path = new ArrayList<>();
path.add(start);
path.add(end);
return path;
}
// Floyd-Warshall with adjacency matrix
public static int[][] floydWarshallWithMatrix(int[][] adjacencyMatrix) {
int n = adjacencyMatrix.length;
int[][] distances = new int[n][n];
int[][] paths = new int[n][n];
// Initialize matrices
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
distances[i][j] = adjacencyMatrix[i][j];
paths[i][j] = i == j ? -1 : i;
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (distances[i][k] != Integer.MAX_VALUE && distances[k][j] != Integer.MAX_VALUE &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
paths[i][j] = paths[k][j];
}
}
}
}
return distances;
}
}JAVASCRIPT Implementation
// Floyd-Warshall Algorithm Implementation in JavaScript
function floydWarshallAlgorithm(graph) {
const vertices = Object.keys(graph);
const n = vertices.length;
// Create distance and path matrices
const distances = {};
const paths = {};
// Initialize distance matrix
for (let i = 0; i < n; i++) {
distances[i] = {};
paths[i] = {};
for (let j = 0; j < n; j++) {
if (i === j) {
distances[i][j] = 0;
} else if (graph[vertices[i]] && graph[vertices[i]][vertices[j]] !== undefined) {
distances[i][j] = graph[vertices[i]][vertices[j]];
paths[i][j] = i;
} else {
distances[i][j] = Infinity;
paths[i][j] = -1;
}
}
}
// Floyd-Warshall algorithm
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (distances[i][k] !== Infinity && distances[k][j] !== Infinity &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
paths[i][j] = paths[k][j];
}
}
}
}
// Check for negative cycles
for (let i = 0; i < n; i++) {
if (distances[i][i] < 0) {
return { hasNegativeCycle: true };
}
}
return { distances, paths, hasNegativeCycle: false };
}
// Get shortest path between two vertices
function getShortestPathFloydWarshall(graph, start, end) {
const result = floydWarshallAlgorithm(graph);
if (result.hasNegativeCycle) {
return null; // Negative cycle detected
}
const vertices = Object.keys(graph);
const startIndex = vertices.indexOf(start);
const endIndex = vertices.indexOf(end);
if (startIndex === -1 || endIndex === -1) {
return null; // Vertex not found
}
if (result.distances[startIndex][endIndex] === Infinity) {
return null; // No path exists
}
// Reconstruct path
const path = [];
let current = endIndex;
while (current !== startIndex) {
path.unshift(vertices[current]);
current = result.paths[startIndex][current];
if (current === -1) break;
}
if (current === startIndex) {
path.unshift(vertices[startIndex]);
}
return {
path,
distance: result.distances[startIndex][endIndex]
};
}
// Floyd-Warshall with adjacency matrix
function floydWarshallWithMatrix(adjacencyMatrix) {
const n = adjacencyMatrix.length;
const distances = [];
const paths = [];
// Initialize matrices
for (let i = 0; i < n; i++) {
distances[i] = [];
paths[i] = [];
for (let j = 0; j < n; j++) {
distances[i][j] = adjacencyMatrix[i][j];
paths[i][j] = i === j ? -1 : i;
}
}
// Floyd-Warshall algorithm
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (distances[i][k] !== Infinity && distances[k][j] !== Infinity &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
paths[i][j] = paths[k][j];
}
}
}
}
return { distances, paths };
}PYTHON Implementation
# Floyd-Warshall Algorithm Implementation in Python
def floyd_warshall_algorithm(graph):
vertices = list(graph.keys())
n = len(vertices)
# Create distance and path matrices
distances = [[float('inf')] * n for _ in range(n)]
paths = [[-1] * n for _ in range(n)]
# Initialize distance matrix
for i in range(n):
distances[i][i] = 0
for j in range(n):
if i != j and vertices[i] in graph and vertices[j] in graph[vertices[i]]:
distances[i][j] = graph[vertices[i]][vertices[j]]
paths[i][j] = i
# Floyd-Warshall algorithm
for k in range(n):
for i in range(n):
for j in range(n):
if distances[i][k] != float('inf') and distances[k][j] != float('inf') and distances[i][k] + distances[k][j] < distances[i][j]:
distances[i][j] = distances[i][k] + distances[k][j]
paths[i][j] = paths[k][j]
# Check for negative cycles
for i in range(n):
if distances[i][i] < 0:
return {'has_negative_cycle': True}
return {'distances': distances, 'paths': paths, 'has_negative_cycle': False}
# Get shortest path between two vertices
def get_shortest_path_floyd_warshall(graph, start, end):
result = floyd_warshall_algorithm(graph)
if result['has_negative_cycle']:
return None # Negative cycle detected
vertices = list(graph.keys())
start_index = vertices.index(start)
end_index = vertices.index(end)
if start_index == -1 or end_index == -1:
return None # Vertex not found
if result['distances'][start_index][end_index] == float('inf'):
return None # No path exists
# Reconstruct path
path = []
current = end_index
while current != start_index:
path.insert(0, vertices[current])
current = result['paths'][start_index][current]
if current == -1:
break
if current == start_index:
path.insert(0, vertices[start_index])
return {
'path': path,
'distance': result['distances'][start_index][end_index]
}
# Floyd-Warshall with adjacency matrix
def floyd_warshall_with_matrix(adjacency_matrix):
n = len(adjacency_matrix)
distances = [row[:] for row in adjacency_matrix]
paths = [[i if i != j else -1 for j in range(n)] for i in range(n)]
# Floyd-Warshall algorithm
for k in range(n):
for i in range(n):
for j in range(n):
if distances[i][k] != float('inf') and distances[k][j] != float('inf') and distances[i][k] + distances[k][j] < distances[i][j]:
distances[i][j] = distances[i][k] + distances[k][j]
paths[i][j] = paths[k][j]
return {'distances': distances, 'paths': paths}
# Get all pairs shortest paths
def get_all_pairs_shortest_paths(graph):
result = floyd_warshall_algorithm(graph)
return result['distances'] if not result['has_negative_cycle'] else None