# What is Bellman-ford

The Bellman-Ford algorithm is a popular algorithm used in graph theory and computer science to find the shortest path between two nodes in a weighted graph. In simple terms, imagine you have a map with different cities connected by roads, and each road has a distance or cost associated with it. The Bellman-Ford algorithm helps you find the shortest distance from one city to another, considering the costs of the roads.

Here's how it works:

1. Initially, the algorithm assumes that the shortest distance from the starting city to all other cities is infinite, except for the starting city itself, which has a distance of 0.

2. It then considers all the roads connecting the cities one by one. For each road, it checks if the distance to the destination city can be reduced by taking the current road. If it can, the algorithm updates the distance of the destination city accordingly.

3. The algorithm repeats step 2 for all the roads in the graph, checking if any distance can be minimized. It does this repeatedly until it has checked all the roads and made all possible updates to the distances.

4. After going through all the roads, if there are still updates being made to the distances, it means that there is a negative cycle in the graph. A negative cycle is a loop of roads that, when traversed, decreases the total distance. In this case, the algorithm can't find a definitive shortest path.

5. If there are no more updates being made after going through all the roads, the algorithm has found the shortest distances from the starting city to all other cities.

To summarize, the Bellman-Ford algorithm starts with an assumption of infinite distances and iteratively updates the distances by considering all the roads until it finds the shortest path or detects a negative cycle.

This algorithm is quite useful in various applications, such as finding the shortest route in a road network or determining the best way to transmit data packets in computer networks.

## Who invented it?

The Bellman-Ford algorithm was independently invented by two mathematicians: Richard Bellman and Lester Ford Jr.

Richard Bellman, an American mathematician and computer scientist, introduced the algorithm in 1958. He is widely recognized for his contributions to dynamic programming and control theory. Bellman's work had a significant impact on various fields, including operations research and computer science.

Lester Ford Jr., another American mathematician, also independently discovered the algorithm around the same time. Ford made notable contributions to graph theory and was known for his work in flow networks, network reliability, and other areas of discrete mathematics.

Both Bellman and Ford made substantial contributions to the development of the algorithm, and it is often referred to as the Bellman-Ford algorithm to honor their independent discoveries.

## Pseudocode

```
function BellmanFord(graph, source):
// Step 1: Initialization
distance[source] = 0
// Step 2: Relax edges repeatedly
for i from 1 to |V|-1:
for each edge (u, v) with weight w in graph:
if distance[u] + w < distance[v]:
distance[v] = distance[u] + w
// Step 3: Check for negative cycles
for each edge (u, v) with weight w in graph:
if distance[u] + w < distance[v]:
return "Graph contains a negative cycle"
// Step 4: Return the shortest distances
return distance
```

In the above pseudocode:

- graph represents the input graph with vertices (V) and edges.
- source is the starting vertex for which we want to find the shortest distances.
- distance is an array that stores the shortest distance from the source to each vertex. Initially, all distances are set to infinity except for the source vertex, which is set to 0.

- Initialization: Set the distance of the source vertex to 0 and all other distances to infinity.
- Relax edges repeatedly: Iterate |V|-1 times (where |V| is the number of vertices) and check if there is a shorter path from the source to each destination vertex by considering each edge. If a shorter path is found, update the distance.
- Check for negative cycles: Iterate through all the edges again and check if there is a further improvement in the distances. If such an improvement is found, it means there is a negative cycle in the graph.
- Return the shortest distances: After completing the iterations, return the array distance that contains the shortest distances from the source vertex to all other vertices.

## Sample Code

```
// C++ code snippet
#include <iostream>
#include <vector>
// Structure to represent an edge in the graph
struct Edge {
int source, destination, weight;
};
// Function to find the shortest paths using Bellman-Ford algorithm
std::vector < int> BellmanFord(std::vector < Edge>& graph, int V, int source) {
std::vector < int> distance(V, INT_MAX);
distance[source] = 0;
// Relax edges repeatedly
for (int i = 1; i < V - 1; ++i) {
for (const auto& edge : graph) {
int u = edge.source;
int v = edge.destination;
int w = edge.weight;
if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
distance[v] = distance[u] + w;
}
}
}
// Check for negative cycles
for (const auto& edge : graph) {
int u = edge.source;
int v = edge.destination;
int w = edge.weight;
if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
std::cout << "Graph contains a negative cycle." << std::endl;
return {}; // Return an empty vector to indicate failure
}
}
return distance;
}
int main() {
int V, E;
std::cout << "Enter the number of vertices: ";
std::cin >> V;
std::cout << "Enter the number of edges: ";
std::cin >> E;
std::vector < Edge> graph(E);
std::cout << "Enter the source, destination, and weight of each edge:" << std::endl;
for (int i = 0; i < E; ++i) {
std::cin >> graph[i].source >> graph[i].destination >> graph[i].weight;
}
int source;
std::cout << "Enter the source vertex: ";
std::cin >> source;
std::vector < int> distances = BellmanFord(graph, V, source);
// Output the shortest distances
std::cout << "Shortest distances from source vertex " << source << ":" << std::endl;
for (int i = 0; i < V; ++i) {
if (distances[i] == INT_MAX) {
std::cout << "Vertex " << i << ": Infinity" << std::endl;
} else {
std::cout << "Vertex " << i << ": " << distances[i] << std::endl;
}
}
return 0;
}
```

```
# Python code snippet
class Edge:
def __init__(self, source, destination, weight):
self.source = source
self.destination = destination
self.weight = weight
def BellmanFord(graph, V, source):
distance = [float('inf')] * V
distance[source] = 0
# Relax edges repeatedly
for _ in range(V - 1):
for edge in graph:
u = edge.source
v = edge.destination
w = edge.weight
if distance[u] != float('inf') and distance[u] + w < distance[v]:
distance[v] = distance[u] + w
# Check for negative cycles
for edge in graph:
u = edge.source
v = edge.destination
w = edge.weight
if distance[u] != float('inf') and distance[u] + w < distance[v]:
print("Graph contains a negative cycle")
return []
return distance
if __name__ == "__main__":
V = int(input("Enter the number of vertices: "))
E = int(input("Enter the number of edges: "))
graph = []
print("Enter the source, destination, and weight of each edge:")
for _ in range(E):
source, destination, weight = map(int, input().split())
graph.append(Edge(source, destination, weight))
source = int(input("Enter the source vertex: "))
distances = BellmanFord(graph, V, source)
# Output the shortest distances
print("Shortest distances from source vertex", source, ":")
for i in range(V):
if distances[i] == float('inf'):
print("Vertex", i, ": Infinity")
else:
print("Vertex", i, ":", distances[i])
```

```
import java.util.Arrays;
import java.util.Scanner;
class Edge {
int source, destination, weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
class BellmanFord {
static void bellmanFord(Edge[] graph, int V, int source) {
int[] distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source] = 0;
// Relax edges repeatedly
for (int i = 1; i < V - 1; i++) {
for (Edge edge : graph) {
int u = edge.source;
int v = edge.destination;
int w = edge.weight;
if (distance[u] != Integer.MAX_VALUE && distance[u] + w < distance[v]) {
distance[v] = distance[u] + w;
}
}
}
// Check for negative cycles
for (Edge edge : graph) {
int u = edge.source;
int v = edge.destination;
int w = edge.weight;
if (distance[u] != Integer.MAX_VALUE && distance[u] + w < distance[v]) {
System.out.println("Graph contains a negative cycle");
return;
}
}
// Print the shortest distances
System.out.println("Shortest distances from source vertex " + source + ":");
for (int i = 0; i < V; i++) {
if (distance[i] == Integer.MAX_VALUE) {
System.out.println("Vertex " + i + ": Infinity");
} else {
System.out.println("Vertex " + i + ": " + distance[i]);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of vertices: ");
int V = scanner.nextInt();
System.out.print("Enter the number of edges: ");
int E = scanner.nextInt();
Edge[] graph = new Edge[E];
System.out.println("Enter the source, destination, and weight of each edge:");
for (int i = 0; i < E; i++) {
int source = scanner.nextInt();
int destination = scanner.nextInt();
int weight = scanner.nextInt();
graph[i] = new Edge(source, destination, weight);
}
System.out.print("Enter the source vertex: ");
int source = scanner.nextInt();
bellmanFord(graph, V, source);
}
}
```

## Time and Space Complexity

Time Complexity:

The Bellman-Ford algorithm consists of two main nested loops. The outer loop runs V-1 times, where V is the number of vertices in the graph. The inner loop iterates through all the edges in the graph. Therefore, the overall time complexity of the algorithm is O(V * E), where V is the number of vertices and E is the number of edges in the graph.

In the worst case, where the graph is dense and has a large number of edges, the time complexity can be close to O(V^3). However, in practice, it often performs better, especially when the graph is sparse or has a small number of edges.

Space Complexity:

The space complexity of the Bellman-Ford algorithm is O(V), where V is the number of vertices in the graph. This is because the algorithm requires storing the distances from the source vertex to all other vertices in the distance array, which has a length equal to the number of vertices.

Additionally, the algorithm may use additional space to represent the graph, such as an adjacency list or matrix. The space complexity of these data structures depends on the specific implementation and can vary from O(V + E) for an adjacency list representation to O(V^2) for an adjacency matrix representation.

It's important to note that the Bellman-Ford algorithm has a relatively higher time complexity compared to other shortest path algorithms, such as Dijkstra's algorithm or the A* algorithm. However, the Bellman-Ford algorithm has the advantage of being able to handle graphs with negative edge weights and detect negative cycles, which those other algorithms cannot do.

## Advantages

1. Handles negative edge weights: The Bellman-Ford algorithm can handle graphs with negative edge weights. This makes it suitable for scenarios where negative weights represent gains or benefits in certain contexts.

2. Detects negative cycles: The algorithm can detect the presence of negative cycles in a graph. If there is a negative cycle reachable from the source vertex, the algorithm will indicate that there is no definitive shortest path, which can be useful in various applications.

3. Flexibility in graph types: The Bellman-Ford algorithm can be used with various types of graphs, including directed and undirected graphs, as well as graphs with both positive and negative edge weights. This flexibility makes it applicable in a wide range of scenarios.

## Disadvantages

1. Slower time complexity: The Bellman-Ford algorithm has a time complexity of O(V * E), which can be relatively slow compared to other shortest path algorithms, such as Dijkstra's algorithm (O((V + E) * log(V))) or the A* algorithm (typically faster with appropriate heuristics). This makes the Bellman-Ford algorithm less efficient for large graphs, especially when E is close to V^2.

2. Redundant iterations: In the worst case, the algorithm requires V-1 iterations to guarantee the shortest paths. However, in many practical cases, the algorithm may converge before reaching the maximum number of iterations. Redundant iterations can impact the overall performance, especially in sparse graphs or scenarios where the algorithm converges quickly.

3. Space complexity: The space complexity of the Bellman-Ford algorithm is O(V), which is relatively efficient. However, for very large graphs, this space usage can still be significant. Additionally, the algorithm may require additional space to represent the graph, depending on the chosen data structure, which can impact the overall memory usage.

4. Less efficient for non-negative graphs: If the graph contains only non-negative edge weights, other algorithms such as Dijkstra's algorithm can provide faster and more efficient solutions. The Bellman-Ford algorithm's ability to handle negative weights comes at the cost of increased complexity, making it less optimal for non-negative scenarios.

Considering these advantages and disadvantages, the Bellman-Ford algorithm is a valuable tool when dealing with graphs containing negative edge weights or when the detection of negative cycles is required. However, for scenarios with large graphs and non-negative edge weights, alternative algorithms like Dijkstra's algorithm or the A* algorithm may offer better time and space efficiency.