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