Bellman–Ford Algorithm | C Programming | DSA | Factsprime

Write a Modular C Programming code for Bellman–Ford Algorithm DSA

4 iterations, with (a) is the original graph. (b), (c), (d), (e) correspond to result after each iteration.

Step 1: Let the given source vertex be 0. Initialize all distances as infinite, except the distance to the source itself. The total number of vertices in the graph is 5, so all edges must be processed 4 times.

Step 2: In each iteration, all edges are relaxed as:

• If dist[v] > dist[u] + weight of edge uv, then update dist[v] to
• dist[v] = dist[u] + weight of edge uv

Step 3: This step reports if there is a negative weight cycle in the graph. Again traverse every edge and follow the same algorythm if found print as Negative-Weight cycles

Refer : C Programming HackerRank all solutions for Loops | Arrays | strings | Data Structures | Linked lists | Stacks | Queues | Binary Trees

CODE:

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

#define MAX_VERTICES 100
#define MAX_EDGES 100

struct Edge {
    int start;
    int end;
    int weight;
};

struct Edge edge_list[MAX_EDGES];
int distance[MAX_VERTICES];

void bellman_ford(int num_vertices, int num_edges, int source_vertex) {
    // Initialize distances from source to all vertices as infinite
    for (int i = 0; i < num_vertices; i++) {
        distance[i] = INT_MAX;
    }
    distance[source_vertex] = 0;

    // Relax all edges |num_vertices| - 1 times
    for (int i = 0; i < num_vertices - 1; i++) {
        for (int j = 0; j < num_edges; j++) {
            int u = edge_list[j].start;
            int v = edge_list[j].end;
            int weight = edge_list[j].weight;
            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
            }
        }
    }

    // Check for negative-weight cycles
    for (int i = 0; i < num_edges; i++) {
        int u = edge_list[i].start;
        int v = edge_list[i].end;
        int weight = edge_list[i].weight;
        if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
            printf("Graph contains negative-weight cycle\n");
            return;
        }
    }

    // Print shortest distances from source to all vertices
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < num_vertices; i++) {
        printf("%d \t\t %d\n", i, distance[i]);
    }
}

int main() {
    int num_vertices, num_edges, source_vertex;

    // Read input
    printf("Enter number of vertices, edges, and source vertex: ");
    scanf("%d %d %d", &num_vertices, &num_edges, &source_vertex);
    printf("Enter edge list as start_vertex end_vertex weight:\n");
    for (int i = 0; i < num_edges; i++) {
        scanf("%d %d %d", &edge_list[i].start, &edge_list[i].end, &edge_list[i].weight);
    }

    // Run Bellman-Ford algorithm
    bellman_ford(num_vertices, num_edges, source_vertex);

    return 0;
}

OUTPUT

Enter number of vertices, edges, and source vertex: 5 8 0
Enter edge list as start_vertex end_vertex weight:
0 1 5
0 2 4
1 3 3
1 4 7
2 1 -3
2 3 2
3 4 6
4 2 -2
Vertex   Distance from Source
0                0
1                1
2                4
3                4
4                8

Process returned 0 (0x0)   execution time : 5.522 s
Press any key to continue.

Please find some more codes of Loops, Condition Statements, 1D Arrays, 2D Arrays, Strings, Pointers, Data Structures, Files, Linked lists, Stacks, Queues, Binary Trees, MISC, Solved model question papers & Hacker Rank all solutions on the below page:

Top 100+ C Programming codes – KLE Technological University