Bellman-Ford Algorithm

The Bellman-Ford Algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted, directed graph. Unlike Dijkstra's Algorithm, the Bellman-Ford Algorithm can handle graphs with negative edge weights but detects and handles negative weight cycles.

How Bellman-Ford Algorithm Works

1. Initialization:

   • Initialize the distance to the source vertex as 0 and all other distances as infinity.

2. Relaxation:

   • Repeat (|V| - 1) times, where (|V|) is the number of vertices:
     • For each edge (u, v) with weight w, if the distance to vertex u plus w is less than the current distance to vertex v, update the distance to v.

3. Negative Cycle Detection:

   • Run an additional pass over all edges to check for negative weight cycles. If any distance can be further reduced, it indicates a negative weight cycle.

Key Features

• Single-Source Shortest Path: Bellman-Ford finds the shortest paths from one source vertex to all other vertices in a weighted graph.

• Handles Negative Weights: It can handle graphs with negative edge weights and detect negative weight cycles.

Efficiency

• Time Complexity: The time complexity of the Bellman-Ford Algorithm is O(V * E), where V is the number of vertices and E is the number of edges. In practice, it is less efficient than Dijkstra's Algorithm but more versatile.

• Space Complexity: The space complexity is O(V), where V is the number of vertices.

Applications

• Routing Protocols: Bellman-Ford is used in network routing protocols like RIP (Routing Information Protocol).

• Traffic Engineering: It can be applied in optimizing traffic routes and resource allocation in transportation and telecommunication networks.

• Robustness: Bellman-Ford's ability to handle negative weights and detect cycles makes it suitable for applications where graph reliability is important.

Limitations

• Less Efficient for Dense Graphs: The algorithm's time complexity can make it less efficient for dense graphs with many edges.

• Not Suitable for Large Networks: In large networks, more efficient algorithms like Dijkstra's Algorithm or variants may be preferred.

Bellman-Ford Algorithm Implementation in JavaScript

Here's an example of Bellman-Ford Algorithm implemented in JavaScript:

class Graph {
    constructor(vertices, edges) {
        this.vertices = vertices;
        this.edges = edges;
    }
 
    bellmanFord(source) {
        const distances = {};
        for (const vertex of this.vertices) {
            distances[vertex] = Infinity;
        }
        distances[source] = 0;
 
        for (let i = 0; i < this.vertices.length - 1; i++) {
            for (const { source, destination, weight } of this.edges) {
                if (distances[source] + weight < distances[destination]) {
                    distances[destination] = distances[source] + weight;
                }
            }
        }
 
        for (const { source, destination, weight } of this.edges) {
            if (distances[source] + weight < distances[destination]) {
                console.log("Negative weight cycle detected");
                return;
            }
        }
 
        return distances;
    }
}
 
// Example usage
const vertices = ["A", "B", "C", "D", "E"];
const edges = [
    { source: "A", destination: "B", weight: -1 },
    { source: "A", destination: "C", weight: 4 },
    { source: "B", destination: "C", weight: 3 },
    { source: "B", destination: "D", weight: 2 },
    { source: "D", destination: "B", weight: 1 },
    { source: "C", destination: "D", weight: 5 },
    { source: "D", destination: "E", weight: 3 },
    { source: "C", destination: "E", weight: 2 },
];
const graph = new Graph(vertices, edges);
const sourceVertex = "A";
const shortestDistances = graph.bellmanFord(sourceVertex);
console.log("Shortest Distances from", sourceVertex + ":", shortestDistances);