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)

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

​​

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

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.

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 ! ;)