Bellman-Ford

The Bellman-Ford algorithm is a single-source shortest path algorithm. It's capable of handling graphs with negative edge weights, unlike Dijkstra's algorithm.

However, it's less efficient than Dijkstra's algorithm for graphs with non-negative edge weights.

pseudocode:

function BellmanFord(Graph, source):
    // Step 1: Initialize distances
    for each vertex v in Graph:
        distance[v] = infinity
    distance[source] = 0

    // Step 2: Relax edges repeatedly
    for i from 1 to |V|-1:  // |V| is the number of vertices
        for each edge (u, v) in Graph:
            if distance[u] + weight(u, v) < distance[v]:
                distance[v] = distance[u] + weight(u, v)
                predecessor[v] = u

    // Step 3: Check for negative-weight cycles
    for each edge (u, v) in Graph:
        if distance[u] + weight(u, v) < distance[v]:
            return "Graph contains a negative-weight cycle"

    return distance, predecessor

class Edge {
    constructor(source, destination, weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
}

class Graph {
    constructor(vertices, edges) {
        this.vertices = vertices;
        this.edges = edges;
        this.distances = {};
        this.previous = {};
    }

    initialize(source) {
        for (let vertex of this.vertices) {
            this.distances[vertex] = Infinity;
            this.previous[vertex] = null;
        }
        this.distances[source] = 0;
    }

    relax(edge) {
        let source = edge.source;
        let destination = edge.destination;
        let weight = edge.weight;
        if (this.distances[source] + weight < this.distances[destination]) {
            this.distances[destination] = this.distances[source] + weight;
            this.previous[destination] = source;
        }
    }

    bellmanFord(source) {
        this.initialize(source);

        for (let i = 0; i < this.vertices.length - 1; i++) {
            for (let edge of this.edges) {
                this.relax(edge);
            }
        }

        for (let edge of this.edges) {
            let source = edge.source;
            let destination = edge.destination;
            let weight = edge.weight;
            if (this.distances[source] + weight < this.distances[destination]) {
                console.log("Graph contains negative-weight cycle");
                return;
            }
        }

        console.log("Shortest distances:", this.distances);
        console.log("Previous nodes:", this.previous);
    }
}

// Example usage:
let vertices = ['A', 'B', 'C', 'D', 'E'];
let edges = [
    new Edge('A', 'B', -1),
    new Edge('A', 'C', 4),
    new Edge('B', 'C', 3),
    new Edge('B', 'D', 2),
    new Edge('D', 'B', 1),
    new Edge('D', 'C', 5),
    new Edge('E', 'D', -3)
];

let graph = new Graph(vertices, edges);
graph.bellmanFord('A');

In this example, the graph is represented as a collection of vertices and edges.

The bellmanFord function performs the Bellman-Ford algorithm to find the shortest paths from a given source vertex to all other vertices in the graph.

The algorithm initializes distances to all vertices as Infinity except the source vertex, which is set to 0.

Then, it iterates over all edges multiple times, updating the distances until convergence.

Finally, it checks for negative-weight cycles and prints the shortest distances and previous nodes.