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

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation system that needs to find the shortest path in a road network. Some roads have toll discounts, which can be represented as negative weights. You will implement the Bellman Ford algorithm to handle these negative weights and find the shortest path from a starting city to all other cities.

🎯 Goal: Build a C program that uses the Bellman Ford algorithm to find the shortest distances from a start vertex to all other vertices in a graph that may contain negative edge weights.

📋 What You'll Learn

Create a graph using an edge list representation with exact edges and weights

Define the number of vertices and edges as constants

Implement the Bellman Ford algorithm to update shortest distances

Print the shortest distances from the start vertex after running the algorithm

💡 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. Bellman Ford helps find shortest paths even with such negative weights.

💼 Career

Understanding Bellman Ford algorithm is important for software engineers working on graph problems, network routing, and optimization tasks where negative weights can occur.

1

Create the graph edges and constants

Create constants V with value 5 and E with value 8. Then create a struct called Edge with three integer members: src, dest, and weight. Finally, create an array called edges of type Edge with exactly these 8 edges: (0, 1, -1), (0, 2, 4), (1, 2, 3), (1, 3, 2), (1, 4, 2), (3, 2, 5), (3, 1, 1), (4, 3, -3).

DSA C

# Define constants V and E
// Define struct Edge with src, dest, weight
// Create array edges with given 8 edges

Hint

Use #define for constants. Define the struct with three int members. Initialize the array with the exact edges given.

2

Initialize distance array and start vertex

Create an integer array called dist of size V. Initialize all elements of dist to 1000000 (representing infinity). Then create an integer variable called start and set it to 0.

DSA C

#include 

#define V 5
#define E 8

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[E] = {
    {0, 1, -1},
    {0, 2, 4},
    {1, 2, 3},
    {1, 3, 2},
    {1, 4, 2},
    {3, 2, 5},
    {3, 1, 1},
    {4, 3, -3}
};

// Initialize dist array and start vertex
// Your code here

Hint

Use a loop from 0 to V-1 to set dist[i] to a large number. Set dist[start] to 0.

3

Implement the Bellman Ford relaxation loop

Write a function called bellman_ford that takes no arguments. Inside it, run a loop from i = 1 to V - 1. Inside this loop, run another loop from j = 0 to E - 1. For each edge, if dist[edges[j].src] + edges[j].weight < dist[edges[j].dest], update dist[edges[j].dest] to dist[edges[j].src] + edges[j].weight. Call initialize_distances() before this function.

DSA C

void bellman_ford() {
    initialize_distances();
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int w = edges[j].weight;
            if (dist[u] != 1000000 && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
int main() {
    // Call bellman_ford and print distances
    // Your code here
    return 0;

Hint

Use two nested loops: outer from 1 to V-1, inner from 0 to E-1. Update distances if a shorter path is found.

4

Print the shortest distances

In the main function, call bellman_ford(). Then print the shortest distances from the start vertex to all vertices in the format: Vertex X: Distance Y where X is the vertex number and Y is the distance stored in dist[X]. Use a loop from 0 to V - 1.

DSA C

#include 

#define V 5
#define E 8

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[E] = {
    {0, 1, -1},
    {0, 2, 4},
    {1, 2, 3},
    {1, 3, 2},
    {1, 4, 2},
    {3, 2, 5},
    {3, 1, 1},
    {4, 3, -3}
};

int dist[V];
int start = 0;

void initialize_distances() {
    for (int i = 0; i < V; i++) {
        dist[i] = 1000000;
    }
    dist[start] = 0;
}

void bellman_ford() {
    initialize_distances();
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int w = edges[j].weight;
            if (dist[u] != 1000000 && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
}

int main() {
    // Call bellman_ford and print distances
    // Your code here
    return 0;
}

Hint

Call bellman_ford() first. Then loop from 0 to V-1 and print each vertex and its distance. Print "Infinity" if distance is 1000000.

Practice

1. What is the main advantage of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

easy

A. It only works on directed acyclic graphs.

B. It runs faster on all graphs.

C. It uses less memory.

D. It can handle graphs with negative weight edges.

Solution

1. Step 1: Understand the limitation of Dijkstra's algorithm

   Dijkstra's algorithm cannot correctly handle graphs with negative weight edges because it assumes that once a node's shortest path is found, it cannot be improved.

2. Step 2: Recognize Bellman-Ford's capability

   Bellman-Ford algorithm can handle negative weight edges and detect negative weight cycles, making it more versatile.

3. Final Answer:

   It can handle graphs with negative weight edges. -> Option D

4. Quick Check:

   Negative weights handled = A [OK]

Hint: Bellman-Ford works with negative edges; Dijkstra does not [OK]

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Assuming it uses less memory
• Believing it only works on acyclic graphs

2. Which of the following is the correct way to initialize the distance array in Bellman-Ford algorithm in C?

easy

A. int dist[V]; for(int i=0; i

B. int dist[V]; for(int i=0; i

C. int dist[V]; for(int i=0; i

D. int dist[V]; for(int i=0; i

Solution

1. Step 1: Understand distance initialization

   Distances to all vertices except the source should be set to a very large number (infinity), here represented by INT_MAX, to indicate they are initially unreachable.

2. Step 2: Set source distance to zero

   The distance to the source vertex itself must be zero because the shortest path from source to source is zero.

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize all to max, source to 0 = C [OK]

Hint: Set all distances to INT_MAX except source = 0 [OK]

Common Mistakes:

• Initializing all distances to zero
• Using -1 for unreachable distances
• Setting all distances to source index

3. What will be the output distances array after running Bellman-Ford on this graph with edges:
edges = [(0,1,4), (0,2,5), (1,2,-3), (2,3,4)] starting from source 0?

medium

A. [0, 4, 1, 5]

B. [0, 4, 1, 9]

C. [0, 4, 5, 9]

D. [0, 4, -3, 4]

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF]

2. Step 2: Relax edges repeatedly

   First iteration:
   dist[1] = min(INF, 0+4) = 4
   dist[2] = min(INF, 0+5) = 5
   dist[2] = min(5, 4 + (-3)) = 1
   dist[3] = min(INF, 1 + 4) = 5
   Second iteration:
   dist[1] stays 4
   dist[2] stays 1
   dist[3] stays 5
   No further updates.

3. Final distances:

   [0, 4, 1, 5]

4. Final Answer:

   [0, 4, 1, 5] -> Option A

5. Quick Check:

   Relax edges to update distances = A [OK]

Hint: Relax edges V-1 times to update shortest paths [OK]

Common Mistakes:

• Not relaxing edges enough times
• Ignoring negative edge effect
• Wrong initial distances

4. Identify the error in this Bellman-Ford code snippet in C:

for (int i = 0; i < V; i++) {
  for (int j = 0; j < E; j++) {
    int u = edges[j].src;
    int v = edges[j].dest;
    int w = edges[j].weight;
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. The outer loop should run V-1 times, not V times.

B. The inner loop should run V times, not E times.

C. The distance array is not initialized.

D. The weight comparison should be dist[v] + w < dist[u].

Solution

1. Step 1: Check loop iteration count

   Bellman-Ford requires relaxing edges exactly V-1 times to find shortest paths correctly.

2. Step 2: Identify the incorrect loop count

   The outer loop runs V times here, which is one extra iteration and unnecessary.

3. Final Answer:

   The outer loop should run V-1 times, not V times. -> Option A

4. Quick Check:

   Outer loop runs V-1 times = D [OK]

Hint: Relax edges exactly V-1 times for correct shortest paths [OK]

Common Mistakes:

• Running outer loop V times instead of V-1
• Confusing inner loop count with vertex count
• Incorrect weight comparison direction

5. Given a graph with edges
[(0,1,1), (1,2,-1), (2,3,-1), (3,1,-1)], what will Bellman-Ford detect when run from source 0?

hard

A. It will run infinitely without stopping.

B. It will find shortest paths without any issues.

C. It will detect a negative weight cycle.

D. It will give incorrect distances but no error.

Solution

1. Step 1: Analyze the cycle in the graph

   The edges (1->2), (2->3), and (3->1) form a cycle with total weight -1 + -1 + -1 = -3, which is negative.

2. Step 2: Understand Bellman-Ford's negative cycle detection

   Bellman-Ford detects negative weight cycles by checking for further relaxation after V-1 iterations. Here, it will detect the negative cycle.

3. Final Answer:

   It will detect a negative weight cycle. -> Option C

4. Quick Check:

   Negative cycle detected = A [OK]

Hint: Negative cycle if distances keep decreasing after V-1 relaxations [OK]

Common Mistakes:

• Assuming algorithm runs infinitely
• Believing it finds shortest paths despite negative cycle
• Ignoring cycle detection step