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.