AntInLoop

Bellman–Ford Algorithm Code Implementations

Complete Bellman–Ford Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Bellman–Ford Algorithm Guide · Launch Interactive Visualizer

C++ Implementation

// Bellman-Ford Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <limits>

class BellmanFordAlgorithm {
public:
    static std::unordered_map<int, int> bellmanFordAlgorithm(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start) {
        std::unordered_map<int, int> distances;
        std::unordered_map<int, int> previous;
        std::vector<int> vertices;
        
        // Get all vertices
        for (const auto& [vertex, neighbors] : graph) {
            vertices.push_back(vertex);
        }
        
        // Initialize distances
        for (int vertex : vertices) {
            distances[vertex] = std::numeric_limits<int>::max();
        }
        distances[start] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices.size() - 1; i++) {
            for (int vertex : vertices) {
                auto it = graph.find(vertex);
                if (it != graph.end()) {
                    for (const auto& [neighbor, weight] : it->second) {
                        if (distances[vertex] != std::numeric_limits<int>::max() && 
                            distances[vertex] + weight < distances[neighbor]) {
                            distances[neighbor] = distances[vertex] + weight;
                            previous[neighbor] = vertex;
                        }
                    }
                }
            }
        }
        
        // Check for negative cycles
        for (int vertex : vertices) {
            auto it = graph.find(vertex);
            if (it != graph.end()) {
                for (const auto& [neighbor, weight] : it->second) {
                    if (distances[vertex] != std::numeric_limits<int>::max() && 
                        distances[vertex] + weight < distances[neighbor]) {
                        return {}; // Negative cycle detected
                    }
                }
            }
        }
        
        return distances;
    }
    
    // Bellman-Ford with edge list representation
    static std::unordered_map<int, int> bellmanFordWithEdgeList(const std::vector<std::tuple<int, int, int>>& edges, 
                                                               const std::unordered_set<int>& vertices, int start) {
        std::unordered_map<int, int> distances;
        std::unordered_map<int, int> previous;
        
        // Initialize distances
        for (int vertex : vertices) {
            distances[vertex] = std::numeric_limits<int>::max();
        }
        distances[start] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices.size() - 1; i++) {
            for (const auto& edge : edges) {
                int from = std::get<0>(edge);
                int to = std::get<1>(edge);
                int weight = std::get<2>(edge);
                
                if (distances[from] != std::numeric_limits<int>::max() && 
                    distances[from] + weight < distances[to]) {
                    distances[to] = distances[from] + weight;
                    previous[to] = from;
                }
            }
        }
        
        // Check for negative cycles
        for (const auto& edge : edges) {
            int from = std::get<0>(edge);
            int to = std::get<1>(edge);
            int weight = std::get<2>(edge);
            
            if (distances[from] != std::numeric_limits<int>::max() && 
                distances[from] + weight < distances[to]) {
                return {}; // Negative cycle detected
            }
        }
        
        return distances;
    }
    
    // Get shortest path from start to end
    static std::vector<int> getShortestPathBellmanFord(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start, int end) {
        auto distances = bellmanFordAlgorithm(graph, start);
        std::unordered_map<int, int> previous;
        
        if (distances.empty()) {
            return {}; // Negative cycle detected
        }
        
        if (distances[end] == std::numeric_limits<int>::max()) {
            return {}; // No path exists
        }
        
        std::vector<int> path;
        int current = end;
        
        while (current != start) {
            path.insert(path.begin(), current);
            current = previous[current];
        }
        path.insert(path.begin(), start);
        
        return path;
    }
};

JAVA Implementation

// Bellman-Ford Algorithm Implementation in Java
import java.util.*;

public class BellmanFordAlgorithm {
    public static Map<Integer, Integer> bellmanFordAlgorithm(Map<Integer, Map<Integer, Integer>> graph, int start) {
        Map<Integer, Integer> distances = new HashMap<>();
        Map<Integer, Integer> previous = new HashMap<>();
        Set<Integer> vertices = graph.keySet();
        
        // Initialize distances
        for (int vertex : vertices) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices.size() - 1; i++) {
            for (int vertex : vertices) {
                Map<Integer, Integer> edges = graph.getOrDefault(vertex, new HashMap<>());
                for (Map.Entry<Integer, Integer> edge : edges.entrySet()) {
                    int neighbor = edge.getKey();
                    int weight = edge.getValue();
                    
                    if (distances.get(vertex) != Integer.MAX_VALUE && 
                        distances.get(vertex) + weight < distances.get(neighbor)) {
                        distances.put(neighbor, distances.get(vertex) + weight);
                        previous.put(neighbor, vertex);
                    }
                }
            }
        }
        
        // Check for negative cycles
        for (int vertex : vertices) {
            Map<Integer, Integer> edges = graph.getOrDefault(vertex, new HashMap<>());
            for (Map.Entry<Integer, Integer> edge : edges.entrySet()) {
                int neighbor = edge.getKey();
                int weight = edge.getValue();
                
                if (distances.get(vertex) != Integer.MAX_VALUE && 
                    distances.get(vertex) + weight < distances.get(neighbor)) {
                    return null; // Negative cycle detected
                }
            }
        }
        
        return distances;
    }
    
    // Bellman-Ford with edge list representation
    public static Map<Integer, Integer> bellmanFordWithEdgeList(List<int[]> edges, Set<Integer> vertices, int start) {
        Map<Integer, Integer> distances = new HashMap<>();
        Map<Integer, Integer> previous = new HashMap<>();
        
        // Initialize distances
        for (int vertex : vertices) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices.size() - 1; i++) {
            for (int[] edge : edges) {
                int from = edge[0];
                int to = edge[1];
                int weight = edge[2];
                
                if (distances.get(from) != Integer.MAX_VALUE && 
                    distances.get(from) + weight < distances.get(to)) {
                    distances.put(to, distances.get(from) + weight);
                    previous.put(to, from);
                }
            }
        }
        
        // Check for negative cycles
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            
            if (distances.get(from) != Integer.MAX_VALUE && 
                distances.get(from) + weight < distances.get(to)) {
                return null; // Negative cycle detected
            }
        }
        
        return distances;
    }
    
    // Get shortest path from start to end
    public static List<Integer> getShortestPathBellmanFord(Map<Integer, Map<Integer, Integer>> graph, int start, int end) {
        Map<Integer, Integer> distances = bellmanFordAlgorithm(graph, start);
        Map<Integer, Integer> previous = new HashMap<>();
        
        if (distances == null) {
            return null; // Negative cycle detected
        }
        
        if (distances.get(end) == Integer.MAX_VALUE) {
            return null; // No path exists
        }
        
        List<Integer> path = new ArrayList<>();
        int current = end;
        
        while (current != start) {
            path.add(0, current);
            current = previous.get(current);
        }
        path.add(0, start);
        
        return path;
    }
}

JAVASCRIPT Implementation

// Bellman-Ford Algorithm Implementation in JavaScript
function bellmanFordAlgorithm(graph, start) {
  const vertices = Object.keys(graph);
  const distances = {};
  const previous = {};
  
  // Initialize distances
  for (const vertex of vertices) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;
  
  // Relax edges V-1 times
  for (let i = 0; i < vertices.length - 1; i++) {
    for (const vertex of vertices) {
      const edges = graph[vertex] || {};
      for (const neighbor in edges) {
        const weight = edges[neighbor];
        if (distances[vertex] !== Infinity && distances[vertex] + weight < distances[neighbor]) {
          distances[neighbor] = distances[vertex] + weight;
          previous[neighbor] = vertex;
        }
      }
    }
  }
  
  // Check for negative cycles
  for (const vertex of vertices) {
    const edges = graph[vertex] || {};
    for (const neighbor in edges) {
      const weight = edges[neighbor];
      if (distances[vertex] !== Infinity && distances[vertex] + weight < distances[neighbor]) {
        return { hasNegativeCycle: true };
      }
    }
  }
  
  return { distances, previous, hasNegativeCycle: false };
}

// Bellman-Ford with edge list representation
function bellmanFordWithEdgeList(edges, vertices, start) {
  const distances = {};
  const previous = {};
  
  // Initialize distances
  for (const vertex of vertices) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;
  
  // Relax edges V-1 times
  for (let i = 0; i < vertices.length - 1; i++) {
    for (const edge of edges) {
      const { from, to, weight } = edge;
      if (distances[from] !== Infinity && distances[from] + weight < distances[to]) {
        distances[to] = distances[from] + weight;
        previous[to] = from;
      }
    }
  }
  
  // Check for negative cycles
  for (const edge of edges) {
    const { from, to, weight } = edge;
    if (distances[from] !== Infinity && distances[from] + weight < distances[to]) {
      return { hasNegativeCycle: true };
    }
  }
  
  return { distances, previous, hasNegativeCycle: false };
}

// Get shortest path from start to end
function getShortestPathBellmanFord(graph, start, end) {
  const result = bellmanFordAlgorithm(graph, start);
  
  if (result.hasNegativeCycle) {
    return null; // Negative cycle detected
  }
  
  if (result.distances[end] === Infinity) {
    return null; // No path exists
  }
  
  const path = [];
  let current = end;
  
  while (current !== undefined) {
    path.unshift(current);
    current = result.previous[current];
  }
  
  return {
    path,
    distance: result.distances[end]
  };
}

PYTHON Implementation

# Bellman-Ford Algorithm Implementation in Python
def bellman_ford_algorithm(graph, start):
    vertices = list(graph.keys())
    distances = {}
    previous = {}
    
    # Initialize distances
    for vertex in vertices:
        distances[vertex] = float('inf')
    distances[start] = 0
    
    # Relax edges V-1 times
    for i in range(len(vertices) - 1):
        for vertex in vertices:
            edges = graph.get(vertex, {})
            for neighbor, weight in edges.items():
                if distances[vertex] != float('inf') and distances[vertex] + weight < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + weight
                    previous[neighbor] = vertex
    
    # Check for negative cycles
    for vertex in vertices:
        edges = graph.get(vertex, {})
        for neighbor, weight in edges.items():
            if distances[vertex] != float('inf') and distances[vertex] + weight < distances[neighbor]:
                return {'has_negative_cycle': True}
    
    return {'distances': distances, 'previous': previous, 'has_negative_cycle': False}

# Bellman-Ford with edge list representation
def bellman_ford_with_edge_list(edges, vertices, start):
    distances = {}
    previous = {}
    
    # Initialize distances
    for vertex in vertices:
        distances[vertex] = float('inf')
    distances[start] = 0
    
    # Relax edges V-1 times
    for i in range(len(vertices) - 1):
        for edge in edges:
            from_vertex, to_vertex, weight = edge
            if distances[from_vertex] != float('inf') and distances[from_vertex] + weight < distances[to_vertex]:
                distances[to_vertex] = distances[from_vertex] + weight
                previous[to_vertex] = from_vertex
    
    # Check for negative cycles
    for edge in edges:
        from_vertex, to_vertex, weight = edge
        if distances[from_vertex] != float('inf') and distances[from_vertex] + weight < distances[to_vertex]:
            return {'has_negative_cycle': True}
    
    return {'distances': distances, 'previous': previous, 'has_negative_cycle': False}

# Get shortest path from start to end
def get_shortest_path_bellman_ford(graph, start, end):
    result = bellman_ford_algorithm(graph, start)
    
    if result['has_negative_cycle']:
        return None  # Negative cycle detected
    
    if result['distances'][end] == float('inf'):
        return None  # No path exists
    
    path = []
    current = end
    
    while current is not None:
        path.insert(0, current)
        current = result['previous'].get(current)
    
    return {
        'path': path,
        'distance': result['distances'][end]
    }

# Bellman-Ford for single source shortest path
def bellman_ford_single_source(graph, start):
    result = bellman_ford_algorithm(graph, start)
    return result['distances'] if not result['has_negative_cycle'] else None