Bellman-Ford Algorithm

Generated on 2025-07-10 01:59:24 Algorithm Cheatsheet for Technical Interviews

---

Bellman-Ford Algorithm Cheatsheet

1. Quick Overview

• What is it? A graph search algorithm that finds the shortest paths from a single source vertex to all other vertices in a weighted graph, even if the graph contains negative edge weights.
• When to use it?
  • When you need to find shortest paths in a graph with potentially negative edge weights.
  • When you need to detect negative cycles in a graph. If a negative cycle exists, the shortest paths are not well-defined.
• Difference from Dijkstra? Dijkstra’s algorithm is more efficient but cannot handle negative edge weights. Bellman-Ford can handle negative edge weights but is slower.

2. Time & Space Complexity

Aspect	Time Complexity	Space Complexity
Bellman-Ford	O(V * E)	O(V)
Negative Cycle Detection	O(V * E)	O(V)

• V = Number of vertices
• E = Number of edges

3. Implementation

Here are example implementations in Python, Java, and C++:

Python:

import math

def bellman_ford(graph, source):
    """
    Finds shortest paths from source to all vertices in graph.
    Detects negative cycles.

    Args:
        graph: A dictionary representing the graph.  Keys are vertices, values are lists of (neighbor, weight) tuples.
        source: The source vertex.

    Returns:
        A tuple containing:
            - distances: A dictionary of shortest distances from source to each vertex.
            - has_negative_cycle: A boolean indicating if a negative cycle exists.
            If a negative cycle is detected, distances may not be accurate.
    """

    distances = {vertex: float('inf') for vertex in graph}
    distances[source] = 0

    # Relax edges V-1 times
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex]:
                if distances[vertex] != float('inf') and distances[vertex] + weight < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + weight

    # Check for negative cycles
    has_negative_cycle = False
    for vertex in graph:
        for neighbor, weight in graph[vertex]:
            if distances[vertex] != float('inf') and distances[vertex] + weight < distances[neighbor]:
                has_negative_cycle = True
                return distances, has_negative_cycle #stop early for efficiency

    return distances, has_negative_cycle

# Example usage:
graph = {
    'A': [('B', -1), ('C', 4)],
    'B': [('C', 3), ('D', 2), ('E', 2)],
    'C': [],
    'D': [('B', 1), ('C', 5)],
    'E': [('D', -3)]
}

distances, has_negative_cycle = bellman_ford(graph, 'A')

print("Shortest Distances:", distances)
print("Negative Cycle:", has_negative_cycle)

graph_negative_cycle = {
    'A': [('B', -1)],
    'B': [('C', -2)],
    'C': [('A', -3)]
}
distances, has_negative_cycle = bellman_ford(graph_negative_cycle, 'A')
print("Negative Cycle graph shortest distances:",distances)
print("Negative Cycle graph negative cycle check:", has_negative_cycle)

Java:

import java.util.*;

public class BellmanFord {

    public static class Edge {
        String source;
        String destination;
        int weight;

        public Edge(String source, String destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    public static class Result {
        Map<String, Integer> distances;
        boolean hasNegativeCycle;

        public Result(Map<String, Integer> distances, boolean hasNegativeCycle) {
            this.distances = distances;
            this.hasNegativeCycle = hasNegativeCycle;
        }
    }


    public static Result bellmanFord(Map<String, List<Edge>> graph, String source) {
        Map<String, Integer> distances = new HashMap<>();
        for (String vertex : graph.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(source, 0);

        // Relax edges V-1 times
        for (int i = 0; i < graph.size() - 1; i++) {
            for (String vertex : graph.keySet()) {
                if (distances.get(vertex) != Integer.MAX_VALUE) {
                    for (Edge edge : graph.get(vertex)) {
                        if (distances.get(vertex) + edge.weight < distances.get(edge.destination)) {
                            distances.put(edge.destination, distances.get(vertex) + edge.weight);
                        }
                    }
                }
            }
        }

        // Check for negative cycles
        boolean hasNegativeCycle = false;
        for (String vertex : graph.keySet()) {
            if (distances.get(vertex) != Integer.MAX_VALUE) {
                for (Edge edge : graph.get(vertex)) {
                    if (distances.get(vertex) + edge.weight < distances.get(edge.destination)) {
                        hasNegativeCycle = true;
                        return new Result(distances, hasNegativeCycle); //stop early for efficiency
                    }
                }
            }
        }

        return new Result(distances, hasNegativeCycle);
    }

    public static void main(String[] args) {
        Map<String, List<Edge>> graph = new HashMap<>();
        graph.put("A", Arrays.asList(new Edge("A", "B", -1), new Edge("A", "C", 4)));
        graph.put("B", Arrays.asList(new Edge("B", "C", 3), new Edge("B", "D", 2), new Edge("B", "E", 2)));
        graph.put("C", new ArrayList<>());
        graph.put("D", Arrays.asList(new Edge("D", "B", 1), new Edge("D", "C", 5)));
        graph.put("E", Arrays.asList(new Edge("E", "D", -3)));

        Result result = bellmanFord(graph, "A");
        System.out.println("Shortest Distances: " + result.distances);
        System.out.println("Negative Cycle: " + result.hasNegativeCycle);

        Map<String, List<Edge>> graph_negative_cycle = new HashMap<>();
        graph_negative_cycle.put("A", Arrays.asList(new Edge("A", "B", -1)));
        graph_negative_cycle.put("B", Arrays.asList(new Edge("B", "C", -2)));
        graph_negative_cycle.put("C", Arrays.asList(new Edge("C", "A", -3)));
        Result result2 = bellmanFord(graph_negative_cycle, "A");
        System.out.println("Negative Cycle graph shortest distances:" + result2.distances);
        System.out.println("Negative Cycle graph negative cycle check:" + result2.hasNegativeCycle);
    }
}

C++:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits>

using namespace std;

struct Edge {
    string source;
    string destination;
    int weight;
};

pair<unordered_map<string, int>, bool> bellmanFord(unordered_map<string, vector<Edge>>& graph, string source) {
    unordered_map<string, int> distances;
    for (auto const& [vertex, edges] : graph) {
        distances[vertex] = numeric_limits<int>::max();
    }
    distances[source] = 0;

    // Relax edges V-1 times
    for (int i = 0; i < graph.size() - 1; i++) {
        for (auto const& [vertex, edges] : graph) {
            if (distances[vertex] != numeric_limits<int>::max()) {
                for (Edge edge : edges) {
                    if (distances[vertex] + edge.weight < distances[edge.destination]) {
                        distances[edge.destination] = distances[vertex] + edge.weight;
                    }
                }
            }
        }
    }

    // Check for negative cycles
    bool hasNegativeCycle = false;
    for (auto const& [vertex, edges] : graph) {
        if (distances[vertex] != numeric_limits<int>::max()) {
            for (Edge edge : edges) {
                if (distances[vertex] + edge.weight < distances[edge.destination]) {
                    hasNegativeCycle = true;
                    return {distances, hasNegativeCycle}; // Stop early for efficiency
                }
            }
        }
    }

    return {distances, hasNegativeCycle};
}

int main() {
    unordered_map<string, vector<Edge>> graph;
    graph["A"] = {{"A", "B", -1}, {"A", "C", 4}};
    graph["B"] = {{"B", "C", 3}, {"B", "D", 2}, {"B", "E", 2}};
    graph["C"] = {};
    graph["D"] = {{"D", "B", 1}, {"D", "C", 5}};
    graph["E"] = {{"E", "D", -3}};

    auto [distances, hasNegativeCycle] = bellmanFord(graph, "A");

    cout << "Shortest Distances: ";
    for (auto const& [vertex, distance] : distances) {
        cout << vertex << ":" << distance << " ";
    }
    cout << endl;
    cout << "Negative Cycle: " << hasNegativeCycle << endl;

    unordered_map<string, vector<Edge>> graph_negative_cycle;
    graph_negative_cycle["A"] = {{"A", "B", -1}};
    graph_negative_cycle["B"] = {{"B", "C", -2}};
    graph_negative_cycle["C"] = {{"C", "A", -3}};

    auto [distances2, hasNegativeCycle2] = bellmanFord(graph_negative_cycle, "A");

    cout << "Negative Cycle graph shortest distances: ";
      for (auto const& [vertex, distance] : distances2) {
        cout << vertex << ":" << distance << " ";
    }
    cout << endl;
    cout << "Negative Cycle graph negative cycle check: " << hasNegativeCycle2 << endl;

    return 0;
}

4. Common Patterns

• Negative Cycle Detection: After V-1 iterations, if you can still relax an edge, it means there’s a negative cycle.
• Path Reconstruction: To reconstruct the shortest path, store the predecessor of each vertex during relaxation. Trace back from the destination to the source.
• Single Source Shortest Path: The primary application.

5. Pro Tips

• Early Termination: If no distances change during an iteration, you can terminate the algorithm early. This can improve performance in some cases.
• Integer Overflow: Be careful of integer overflow when adding edge weights. Use long (Java), long long (C++), or consider using a larger maximum value for infinity.
• Graph Representation: The choice of graph representation (adjacency list vs. adjacency matrix) can affect performance. Adjacency lists are generally preferred for sparse graphs.
• Initialization: Initialize all distances to infinity except for the source vertex, which is initialized to 0.

6. Practice Problems

1. LeetCode 743. Network Delay Time: Determine the time it takes for a signal to reach all nodes in a network. Requires finding shortest paths from a single source. Can use Dijkstra or Bellman-Ford, but Bellman-Ford is useful if edge weights might be negative (though the problem statement typically doesn’t allow it).
2. LeetCode 787. Cheapest Flights Within K Stops: Find the cheapest price from src to dst with at most k stops. Bellman-Ford is well-suited for this because the number of iterations naturally limits the number of stops.
3. Detecting Negative Cycle: Implement a function that specifically detects if a negative cycle exists using Bellman-Ford.

7. Templates

These templates provide a reusable starting point for implementing Bellman-Ford in different languages. They include basic graph representation and the core algorithm structure.

C++ Template:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits>

using namespace std;

struct Edge {
    string source;
    string destination;
    int weight;
};

pair<unordered_map<string, int>, bool> bellmanFord(unordered_map<string, vector<Edge>>& graph, string source) {
    unordered_map<string, int> distances;
    for (auto const& [vertex, edges] : graph) {
        distances[vertex] = numeric_limits<int>::max();
    }
    distances[source] = 0;

    // Relax edges V-1 times
    for (int i = 0; i < graph.size() - 1; i++) {
        for (auto const& [vertex, edges] : graph) {
            if (distances[vertex] != numeric_limits<int>::max()) {
                for (Edge edge : edges) {
                    if (distances[vertex] + edge.weight < distances[edge.destination]) {
                        distances[edge.destination] = distances[vertex] + edge.weight;
                    }
                }
            }
        }
    }

    // Check for negative cycles
    bool hasNegativeCycle = false;
    for (auto const& [vertex, edges] : graph) {
        if (distances[vertex] != numeric_limits<int>::max()) {
            for (Edge edge : edges) {
                if (distances[vertex] + edge.weight < distances[edge.destination]) {
                    hasNegativeCycle = true;
                    return {distances, hasNegativeCycle}; // Stop early for efficiency
                }
            }
        }
    }

    return {distances, hasNegativeCycle};
}

int main() {
    // Example usage (replace with your graph data)
    unordered_map<string, vector<Edge>> graph;
    // graph["A"] = {{"A", "B", 5}, {"A", "C", 2}}; // Example edges

    string source = "A"; // Example source vertex

    auto [distances, hasNegativeCycle] = bellmanFord(graph, source);

    // Print results
    cout << "Shortest Distances: ";
    for (auto const& [vertex, distance] : distances) {
        cout << vertex << ":" << distance << " ";
    }
    cout << endl;
    cout << "Negative Cycle: " << hasNegativeCycle << endl;

    return 0;
}

Python Template:

import math

def bellman_ford(graph, source):
    """
    Finds shortest paths from source to all vertices in graph.
    Detects negative cycles.

    Args:
        graph: A dictionary representing the graph.  Keys are vertices, values are lists of (neighbor, weight) tuples.
        source: The source vertex.

    Returns:
        A tuple containing:
            - distances: A dictionary of shortest distances from source to each vertex.
            - has_negative_cycle: A boolean indicating if a negative cycle exists.
            If a negative cycle is detected, distances may not be accurate.
    """

    distances = {vertex: float('inf') for vertex in graph}
    distances[source] = 0

    # Relax edges V-1 times
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex]:
                if distances[vertex] != float('inf') and distances[vertex] + weight < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + weight

    # Check for negative cycles
    has_negative_cycle = False
    for vertex in graph:
        for neighbor, weight in graph[vertex]:
            if distances[vertex] != float('inf') and distances[vertex] + weight < distances[neighbor]:
                has_negative_cycle = True
                return distances, has_negative_cycle #stop early for efficiency

    return distances, has_negative_cycle

# Example usage:
# graph = {
#     'A': [('B', -1), ('C', 4)],
#     'B': [('C', 3), ('D', 2), ('E', 2)],
#     'C': [],
#     'D': [('B', 1), ('C', 5)],
#     'E': [('D', -3)]
# }

# distances, has_negative_cycle = bellman_ford(graph, 'A')

# print("Shortest Distances:", distances)
# print("Negative Cycle:", has_negative_cycle)

Java Template:

import java.util.*;

public class BellmanFord {

    public static class Edge {
        String source;
        String destination;
        int weight;

        public Edge(String source, String destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    public static class Result {
        Map<String, Integer> distances;
        boolean hasNegativeCycle;

        public Result(Map<String, Integer> distances, boolean hasNegativeCycle) {
            this.distances = distances;
            this.hasNegativeCycle = hasNegativeCycle;
        }
    }


    public static Result bellmanFord(Map<String, List<Edge>> graph, String source) {
        Map<String, Integer> distances = new HashMap<>();
        for (String vertex : graph.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(source, 0);

        // Relax edges V-1 times
        for (int i = 0; i < graph.size() - 1; i++) {
            for (String vertex : graph.keySet()) {
                if (distances.get(vertex) != Integer.MAX_VALUE) {
                    for (Edge edge : graph.get(vertex)) {
                        if (distances.get(vertex) + edge.weight < distances.get(edge.destination)) {
                            distances.put(edge.destination, distances.get(vertex) + edge.weight);
                        }
                    }
                }
            }
        }

        // Check for negative cycles
        boolean hasNegativeCycle = false;
        for (String vertex : graph.keySet()) {
            if (distances.get(vertex) != Integer.MAX_VALUE) {
                for (Edge edge : graph.get(vertex)) {
                    if (distances.get(vertex) + edge.weight < distances.get(edge.destination)) {
                        hasNegativeCycle = true;
                        return new Result(distances, hasNegativeCycle); //stop early for efficiency
                    }
                }
            }
        }

        return new Result(distances, hasNegativeCycle);
    }

    public static void main(String[] args) {
       // Map<String, List<Edge>> graph = new HashMap<>();
        // graph.put("A", Arrays.asList(new Edge("A", "B", -1), new Edge("A", "C", 4)));
        // graph.put("B", Arrays.asList(new Edge("B", "C", 3), new Edge("B", "D", 2), new Edge("B", "E", 2)));
        // graph.put("C", new ArrayList<>());
        // graph.put("D", Arrays.asList(new Edge("D", "B", 1), new Edge("D", "C", 5)));
        // graph.put("E", Arrays.asList(new Edge("E", "D", -3)));

        // Result result = bellmanFord(graph, "A");
        // System.out.println("Shortest Distances: " + result.distances);
        // System.out.println("Negative Cycle: " + result.hasNegativeCycle);
    }
}

This cheatsheet provides a comprehensive overview of the Bellman-Ford algorithm, including practical implementations, tips, and templates for quick reference. Remember to adapt the code and templates to your specific problem and graph representation. Good luck!