Why Bellman Ford Algorithm Negative Weights in DSA C?

The Big Idea

What if some roads actually pay you to travel them? How do you find the cheapest path then?

The Scenario

Imagine you are planning a road trip and want to find the shortest path between cities. Some roads have tolls (positive costs), but others offer discounts (negative costs). Trying to calculate the cheapest route by hand, especially with discounts, is confusing and error-prone.

The Problem

Manually checking every possible path to find the cheapest route is slow and easy to mess up. Negative costs make it even harder because simple methods can get stuck or give wrong answers, missing cheaper routes that use discounts.

The Solution

The Bellman Ford algorithm smartly handles roads with discounts (negative weights). It systematically updates the shortest paths, even if some roads reduce the total cost. It also detects if there is a loop that keeps reducing cost endlessly, which means no solution.

Before vs After

✗ Before

int distances[numCities];
// Manually try all paths and update distances
for (int i = 0; i < numPaths; i++) {
  // Complex checks and updates
}

✓ After

for (int i = 0; i < numCities - 1; i++) {
  for (int j = 0; j < numEdges; j++) {
    // Relax edges to update shortest paths
  }
}

What It Enables

You can reliably find shortest paths in graphs even when some edges reduce total cost, and detect impossible cases.

Real Life Example

Finding the cheapest flight route where some flights offer cashback or discounts, so the total travel cost can be less than expected.

Key Takeaways

Manual path checking is slow and error-prone with negative weights.

Bellman Ford updates shortest paths step-by-step, handling negative edges.

It detects negative cycles where no shortest path exists.