DSA Tutorial

🔁 Bellman-Ford Algorithm in DSA (Using C)

Bellman-Ford Algorithm is used to find the shortest paths from a single source node to all other nodes in a **weighted graph**, and it can also handle **negative weight edges**.

📌 Key Features:

• Handles negative weight edges
• Detects negative weight cycles
• Time Complexity: O(V * E)

💻 C Code for Bellman-Ford Algorithm

#include <stdio.h>
#include <limits.h>

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

void BellmanFord(struct Edge edges[], int V, int E, int src) {
    int dist[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    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 wt = edges[j].weight;

            if (dist[u] != INT_MAX && dist[u] + wt < dist[v])
                dist[v] = dist[u] + wt;
        }
    }

    // Check for negative-weight cycles
    for (int j = 0; j < E; j++) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int wt = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + wt < dist[v]) {
            printf("Graph contains negative weight cycle\\n");
            return;
        }
    }

    printf("Vertex\\tDistance from Source\\n");
    for (int i = 0; i < V; i++)
        printf("%d\\t%d\\n", i, dist[i]);
}

int main() {
    int V = 5;  // Number of vertices
    int E = 8;  // Number of edges
    struct Edge 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}
    };

    BellmanFord(edges, V, E, 0);
    return 0;
}
  

📤 Sample Output

Vertex  Distance from Source
0       0
1       -1
2       2
3       -2
4       1
  

🛠️ Use Cases

• Graphs with negative edge weights
• Currency exchange arbitrage
• Network routing with latency/penalties