The Bellman-Ford Algorithm is a single-source shortest path algorithm used to find the shortest path from a source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, which works only for graphs with non-negative edge weights, Bellman-Ford can handle graphs with negative edge weights and can detect negative weight cycles.
Algorithm
1
2
3
4
5
6
7
8
9
10
INITIALIZE-SINGLE-SOURCE (G, s)
for each vertex i = 1 to V[G] - 1 do
for each edge (u, v) in E[G] do
RELAX (u, v, w)
For each edge (u, v) in E[G] do
if d[u] + w(u, v) < d[v] then
return FALSE
return TRUE
Analysis
The initialization in line 1 takes (v) time. For loop of lines, 2-4 takes O(E) time and for For-loop of lines, 5-7 takes O(E) time. Thus, the Bellman-Ford algorithm runs in O(E) time.
Implementation in C Language
maxVertices represents the maximum number of vertices that can be present in the graph. Input Format: Graph is directed and weighted.
The first two integers must be the number of vertices and edges which must be followed by pairs of vertices that have an edge between them. vertices represent the number of vertices and edges represent the number of edges in the graph.
Source Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
struct edge {
int src;
int dest;
int weight;
};
struct Graph {
int vertex;
int e;
struct edge * edge_list;
};
void bellman_ford(struct Graph *graph, int * dist, int source) {
int i = 0, j = 0;
for (i = 0; i < graph->vertex; i++) {
dist[i] = INT_MAX;
}
dist[source] = 0;
for (j = 0; j <= graph->vertex - 1; j++) {
for (i = 0; i < graph->e; i++) {
if (dist[graph->edge_list[i].dest] > (dist[graph->edge_list[i].src] + graph->edge_list[i].weight)) {
dist[graph->edge_list[i].dest] = dist[graph->edge_list[i].src] + graph->edge_list[i].weight;
}
}
}
}
int main() {
int no_of_vertex, no_of_edges, *dist, i = 0, start_vertex = 0;
struct Graph *graph = (struct Graph *) malloc(sizeof(struct Graph));
printf("Enter number of vertex:");
scanf("%d", &no_of_vertex);
printf("Enter number of edges:");
scanf("%d", &no_of_edges);
printf("Enter the start vertex:");
scanf("%d", &start_vertex);
graph->e = no_of_edges;
graph->vertex = no_of_vertex;
graph->edge_list = (struct edge *) malloc(no_of_edges * sizeof(struct edge));
printf("Enter source destination and weight of the edges:");
for (i = 0; i < no_of_edges; i++) {
scanf("%d%d%d", &graph->edge_list[i].src, &graph->edge_list[i].dest, &graph->edge_list[i].weight);
}
dist = (int * ) malloc(no_of_vertex * sizeof(int));
bellman_ford(graph, dist, start_vertex);
for (i = 0; i < graph->vertex; i++) {
printf("%d %d\n", i, dist[i]);
}
return 0;
}
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.