AntInLoop

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