C Programming: Bellman-Ford Algorithm 🎯

Welcome to our comprehensive guide on the Bellman-Ford Algorithm in C Programming! This tutorial is designed for both beginners and intermediate learners, covering the concept from the ground up.

Understanding Bellman-Ford Algorithm 📝

The Bellman-Ford Algorithm is a popular algorithm in graph theory used for finding the shortest paths in a weighted graph that may contain negative edge weights. It's particularly useful when the graph contains cycles, which is not allowed in Dijkstra's algorithm.

Why Bellman-Ford Algorithm? 💡

The Bellman-Ford Algorithm is versatile and can handle graphs with negative weights and cycles. It's essential for solving problems where these complexities exist, making it a valuable tool in your programming arsenal.

Bellman-Ford Algorithm Steps 📝

Initialize: Set all vertices' distances from the source vertex to infinity, except for the source vertex, whose distance is set to 0.
Relax Edges V - 1 times: For each iteration, update the distance to a vertex through a new path if the new path has a shorter distance.
Check for Negative-Weight Cycle: If, during the relaxation step, an edge's total weight becomes less than the current shortest path, a negative-weight cycle exists.

Bellman-Ford Algorithm Implementation in C 💡

Here's a simple, practical implementation of the Bellman-Ford Algorithm in C:

#include <stdio.h>
#include <limits.h>
#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void bellmanFord(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    dist[src] = 0;

    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < V; j++) {
            for (int k = 0; k < V; k++) {
                if (graph[j][k] && dist[j] != INT_MAX && dist[j] + graph[j][k] < dist[k])
                    dist[k] = dist[j] + graph[j][k];
            }
        }
    }

    if (V > 1) {
        for (int i = 0; i < V; i++)
            if (dist[i] == INT_MAX)
                printf("Graph contains a negative-weight cycle.\n");
        else
            printf("Shortest distance from source vertex %d to each vertex:\n", src);

        for (int i = 0; i < V; i++)
            printf(" %d", dist[i]);
    }
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 0, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 0},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 0, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 0, 0, 0, 0, 6, 7, 0}
    };

    bellmanFord(graph, 0);
    return 0;
}

This tutorial covers the fundamentals of the Bellman-Ford Algorithm in C programming, providing you with a practical understanding to tackle real-world problems. Keep practicing and stay curious! 🎉