Home > Algorithms, C/C++ > Bellman-Ford’s Algorithm – Solving the Shortest Path Problem (negative edges presented)

Bellman-Ford’s Algorithm – Solving the Shortest Path Problem (negative edges presented)

October 7th, 2013 Leave a comment Go to comments

Algorithm Overview

I’ve already written a post about Dijkstra, one of the algorithms I used in my Bachelor’s work. I can’t go on without mentioning the other one. 

Bellman Ford is another algorithm created with the purpose of finding the shortest path between two vertices in a graph. It is a non-greedy algorithm very similar to Dijkstra, with one notable difference – it is capable of detecting negative edges in a graph. It is also slower compared to Dijkstra. 

In practice, Bellman-Ford’s algorithm is used in some distance-vector routing protocols like the Routing Information Protocol which is one of the oldest and is typically no longer used (mainly due its limited hop count). 

 

Pseudocode

The following is a pseudocode for the Bellman-Ford’s algorithm:

Bellman Ford’s algorithm – C++ implementation

Implementing a game

As with Dijkstra, this is an actual game using the algorithm. I’m using Strategy in order to implement the actual runtime selection. 

bellman-ford-screenshot​​

The interface for the algorithm

The interface is very similar to the one used with Dijkstra

​The actual algorithm in C++

The following is the actual implementation of the algorithm. 

BellmanFordImplementation.h

BellmanFordImplementation.cpp

The input/output parameters for the main method are very similar to the ones used in Dijkstra:

  • edges - list of all the edges
  • distances - vector that contains the distance to every vertex from the source. The index of the element is the destination, while the value is the actual path cost. 
  • previous this vector contains the actual shortest path. The index is the vertex, and the value is the vertex before it in the path. 
  • edgenum - the total number of edges
  • numberOfVertices - the total number of vertices

The other part of the algorithm – the BellmanFordShortestPathTo function – is a supportive function that returns the actual shortest path vertices. The first input parameter is the target vertex, while the second is the previous output parameter from the main algorithm function. 

Initializing the adjacency matrix

As for the initialization part, you can use the following code for a rectangular field (and exclude certain vertices for obsticles, for instance)

Again, it’s up to you to modify the code above to improve readability and maintainability according to your needs. 



About the author:

Kosta Hristov (34 Posts)

Hi there ! My name is Kosta Hristov and I currently live in London, England. I've been working as a software engineer for the past 6 years on different mobile, desktop and web IT projects. I started this blog almost one year ago with the idea of helping developers from all around the world in their day to day programming tasks, sharing knowledge on various topics. If you find my articles interesting and you want to know more about me, feel free to contact me via the social links below. ;)




Like the article ? Share it ! ;)


  1. No comments yet.
  1. No trackbacks yet.

Current month ye@r day *


Copyright © Developing the future 2013. Licensed under the CC> BY-NC-ND 3.0 Creative Commons license.       
Audi R8 wallpapers Sony Xperia Z4 Tablet WiFi