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.
#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