Bellman Ford Algorithm Negative Weights in DSA Typescript - Build from Scratch

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation system that needs to find the shortest path between cities. Some roads have toll discounts represented as negative weights. You need to handle these negative weights safely.

🎯 Goal: Build a TypeScript program that uses the Bellman Ford algorithm to find the shortest distances from a starting city to all other cities, even when some roads have negative weights.

📋 What You'll Learn

Create an array of edges representing roads with source, destination, and weight

Create a variable for the number of vertices (cities)

Implement the Bellman Ford algorithm to calculate shortest distances

Detect if there is a negative weight cycle

Print the shortest distances or a message if a negative cycle exists

💡 Why This Matters

🌍 Real World

Navigation systems and routing algorithms often need to handle roads with discounts or penalties, which can be modeled as negative weights.

💼 Career

Understanding Bellman Ford is important for software engineers working on graph algorithms, network routing, and optimization problems.

1

Create the graph edges array

Create a variable called edges as an array of objects with these exact entries: {src: 0, dest: 1, weight: 5}, {src: 1, dest: 2, weight: -2}, {src: 2, dest: 3, weight: 3}, {src: 3, dest: 1, weight: 1}, {src: 0, dest: 3, weight: 10}.

DSA Typescript

// Your code here

Hint

Use an array of objects where each object has src, dest, and weight properties.

2

Set the number of vertices

Create a variable called vertices and set it to 4 to represent the number of cities.

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 5},
  {src: 1, dest: 2, weight: -2},
  {src: 2, dest: 3, weight: 3},
  {src: 3, dest: 1, weight: 1},
  {src: 0, dest: 3, weight: 10}
];
// Your code here

Hint

Count the unique cities from the edges and assign the number to vertices.

3

Implement the Bellman Ford algorithm

Create a function called bellmanFord that takes edges, vertices, and start as parameters. Inside, create a distances array of length vertices filled with Infinity. Set distances[start] to 0. Use a for loop from 0 to vertices - 1 to relax edges. Then check for negative weight cycles by iterating over edges and returning null if a cycle is found. Otherwise, return distances.

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 5},
  {src: 1, dest: 2, weight: -2},
  {src: 2, dest: 3, weight: 3},
  {src: 3, dest: 1, weight: 1},
  {src: 0, dest: 3, weight: 10}
];

const vertices = 4;

// Your code here

Hint

Follow the Bellman Ford steps: initialize distances, relax edges multiple times, then check for negative cycles.

4

Print the shortest distances or negative cycle message

Call bellmanFord(edges, vertices, 0) and store the result in result. If result is null, print "Graph contains a negative weight cycle". Otherwise, print "Shortest distances from vertex 0:" followed by the result array.

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 5},
  {src: 1, dest: 2, weight: -2},
  {src: 2, dest: 3, weight: 3},
  {src: 3, dest: 1, weight: 1},
  {src: 0, dest: 3, weight: 10}
];

const vertices = 4;

function bellmanFord(edges: {src: number; dest: number; weight: number}[], vertices: number, start: number): number[] | null {
  const distances = new Array(vertices).fill(Infinity);
  distances[start] = 0;

  for (let i = 0; i < vertices - 1; i++) {
    for (const edge of edges) {
      if (distances[edge.src] !== Infinity && distances[edge.src] + edge.weight < distances[edge.dest]) {
        distances[edge.dest] = distances[edge.src] + edge.weight;
      }
    }
  }

  for (const edge of edges) {
    if (distances[edge.src] !== Infinity && distances[edge.src] + edge.weight < distances[edge.dest]) {
      return null; // Negative weight cycle detected
    }
  }

  return distances;
}

// Your code here

Hint

Call the function with start vertex 0. Check if the result is null to detect negative cycles. Print the distances array if no cycle.