Bellman Ford Algorithm C Program

By | October 1, 2016

C Program To Implement Bellman Ford Algorithm

Let us learn how to implement Bellman Ford Algorithm in C programming language. This algorithm is also famously known as Bellman – Ford – Moore Algorithm. The algorithm makes use of Queue Data Structure.

What is Bellman Ford Algorithm?

The Bellman-Ford Algorithm is an algorithm that calculates the shortest path from a source vertex to a destination vertex in a weighted graph. A weighted graph consists of the cost or lengths of all the edges in a given graph. This algorithm helps to detect cycles whose edges sum to a negative value which is also known as a

This algorithm helps to detect cycles whose edges sum to a negative value which is also known as a

A weighted graph consists of the cost or lengths of all the edges in a given graph. This algorithm helps to detect cycles whose edges sum to a negative value which is also known as a Negative Cycle.

However, this algorithm is more versatile than Dijkstra’s Algorithm but a little slower in execution. This algorithm can handle graphs with non – negative weights, unlike Dijkstra Algorithm.

This algorithm works efficiently only for Non – Negative weights.

Implementation of Bellman Ford Algorithm in C Programming

Must Read: C Program For Sieve of Eratosthenes Algorithm

Bellman Ford Algorithm

 

  1. Initialize the predecessor of all the vertices to NIL and pathLength of all vertices to Infinity.
  2. Set the pathLength of the source vertex to zero and add it to the Queue.
  3. Delete a vertex from the Queue and set it as the current vertex.
  4. Check all the adjacent vertices of the current vertex. Check minimum weight condition for these vertices and do relabel if needed.
  5. Every vertex is relabeled is inserted into the queue if it is not present in the queue.
  6. Repeat Steps 3, 4 and 5 till the Queue Underflow condition is satisfied. Queue underflow occurs when the Queue becomes Empty.

There are other algorithms that can be used to find the shortest path in a weighted graph such as:

 

C Program To Implement Bellman Ford Algorithm using Queue

 

Must Read: C Program For Implement Warshall’s Algorithm

Output

C Program To Implement Bellman Ford Algorithm using Queue

In case you get any compilation errors or any doubts in this C program for Bellman Ford Algorithm solution for Finding Shortest Path in a weighted graph, let us know about it in the comment section below. Find more about this algorithm on Wikipedia.

2 thoughts on “Bellman Ford Algorithm C Program

  1. Akshay Pawar

    The bellman ford algorithm is an advanced version of the Dijkstra’s algorithm.

    Reply
  2. Rajesh Srivastav

    Thank you so much. The Bellman ford is an an amazing algorithm

    Reply

Let's Discuss