Bellman Ford Implementation in TypeScript.

bellman_ford.ts

class BellmanFord {
  // Graph represented as an adjacency list
  graph: Record<string, Record<string, number>>;

  constructor(graph: Record<string, Record<string, number>>) {
    this.graph = graph;
  }

  bellmanFord(source: string) {
    // Initialize distances and predecessors
    const distances: Record<string, number> = {};
    const predecessors: Record<string, string | null> = {};
    for (const vertex in this.graph) {
      distances[vertex] = Infinity;
      predecessors[vertex] = null;
    }
    distances[source] = 0;

    // Relax edges repeatedly
    for (let i = 0; i < Object.keys(this.graph).length - 1; i++) {
      for (const vertex in this.graph) {
        for (const neighbor in this.graph[vertex]) {
          if (
            distances[vertex] + this.graph[vertex][neighbor] <
            distances[neighbor]
          ) {
            distances[neighbor] =
              distances[vertex] + this.graph[vertex][neighbor];
            predecessors[neighbor] = vertex;
          }
        }
      }
    }

    // Check for negative-weight cycles
    for (const vertex in this.graph) {
      for (const neighbor in this.graph[vertex]) {
        if (
          distances[vertex] + this.graph[vertex][neighbor] <
          distances[neighbor]
        ) {
          throw new Error("Negative-weight cycle detected");
        }
      }
    }

    return { distances, predecessors };
  }
}

// Test data
const graph: Record<string, Record<string, number>> = {
  A: { B: -1, C: 4 },
  B: { C: 3, D: 2, E: 2 },
  C: {},
  D: { B: 1, C: 5 },
  E: { D: -3 },
};

const source = "A";

// Run the algorithm
const bellmanFordInstance = new BellmanFord(graph);
const result = bellmanFordInstance.bellmanFord(source);

console.log("Distances:", result.distances);
console.log("Predecessors:", result.predecessors);

// Result
// Distances: { A: 0, B: -1, C: 2, D: -2, E: 1 }
// Predecessors: { A: null, B: 'A', C: 'B', D: 'E', E: 'B' }