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:
procedure BellmanFord(list vertices, list edges, vertex source) // This implementation takes in a graph, represented as lists of vertices and edges, // and fills two arrays (distance and predecessor) with shortest-path information // Step 1: initialize graph for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "Graph contains a negative-weight cycle"
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.
int WolfHuntAlgorithm::determinePath_BellmanFord(qreal ax, qreal ay, qreal bx, qreal by, int &lastBestRange,
std::vector &pathToTarget, int &direction)
{
int wolfVertex = ax/43 + (ay/43*13);
int rabbitVertex = bx/43 + (by/43*13);
vector min_distance(169);
std::vector previous(1000);
BellmanFord(this->edges, min_distance, previous, this->edges.size(), 169, wolfVertex);
pathToTarget = BellmanFordShortestPathTo(rabbitVertex, previous);
int newBestRange = min_distance[rabbitVertex];
if(pathToTarget[1] == wolfVertex + 1)
{
direction = RIGHT;
} else if(pathToTarget[1] == wolfVertex - 1)
{
direction = LEFT;
} else if(pathToTarget[1] == wolfVertex - 13)
{
direction = UP;
} else if(pathToTarget[1] == wolfVertex + 13)
{
direction = DOWN;
} else if(pathToTarget[1] == wolfVertex - 12)
{
direction = RIGHT_UP;
} else if(pathToTarget[1] == wolfVertex - 14)
{
direction = LEFT_UP;
} else if(pathToTarget[1] == wolfVertex + 12)
{
direction = LEFT_DOWN;
} else if(pathToTarget[1] == wolfVertex + 14)
{
direction = RIGHT_DOWN;
}
...
}
The actual algorithm in C++
The following is the actual implementation of the algorithm.
BellmanFordImplementation.h
#ifndef BELLMANFORD_H
#define BELLMANFORD_H
#include
#include
#include
using namespace std;
#define INFINITY 99999
struct EdgeB {
int source, destination, weight;
EdgeB(int source, int destination, int weight):source(source),
destination(destination), weight(weight)
{
}
};
void BellmanFord(vector edges, vector &distances, vector &previous, int edgenum, int numberOfVertexes, int source);
vector BellmanFordShortestPathTo(int target, vector &previous);
#endif
BellmanFordImplementation.cpp
#include "BellmanFordImplementation.h"
#include
using namespace std;
void BellmanFord(vector edges, vector &distances, vector &previous, int edgenum, int numberOfVertexes, int source)
{
for (int i=0; i < numberOfVertexes; ++i)
distances[i] = 999;
distances[source] = 0;
for (int v=0; v < numberOfVertexes; ++v){
for (int e=0; e < edgenum; ++e){
if (distances[edges[e].source] != INFINITY) {
if (distances[edges[e].source] + edges[e].weight < distances[edges[e].destination]){
distances[edges[e].destination] = distances[edges[e].source] + edges[e].weight;
previous[edges[e].destination] = edges[e].source;
}
}
}
}
for (int e=0; e < edgenum; ++e){
if (distances[edges[e].source] + edges[e].weight < distances[edges[e].destination]){
std::cout << "The graph contains negative edges.";
}
}
}
vector BellmanFordShortestPathTo(int target, vector &previous)
{
std::vector path;
path.push_back(target);
int nextVertex = target;
while (previous.at(nextVertex) != 0) {
std::vector::iterator it = path.begin();
path.insert(it, previous.at(nextVertex));
nextVertex = previous.at(nextVertex);
}
return path;
}
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)
void WolfHuntAlgorithm::initializeFieldGraph_BellmanFord(QList *bearPositions)
{
VERTEX vertexPosition;
for (int i = 0; i < 168; ++i) {
if(i == 0)
{
vertexPosition = V_LEFT_UP;
} else if (i == 12)
{
vertexPosition = V_RIGHT_UP;
} else if (i == 156)
{
vertexPosition = V_LEFT_DOWN;
} else if(i == 168)
{
vertexPosition = V_RIGHT_DOWN;
}
for (int j = 1; j < 12; ++j) {
if(i == j)
{
vertexPosition = V_UP_BORDER;
break;
}
}
for (int j = 157; j < 168; ++j) {
if(i == j)
{
vertexPosition = V_DOWN_BORDER;
break;
}
}
for (int j = 13; j < 156; j = j + 13) {
if(i == j)
{
vertexPosition = V_LEFT_BORDER;
break;
}
}
for (int j = 25; j < 168; j = j + 13) {
if(i == j)
{
vertexPosition = V_RIGHT_BORDER;
break;
}
}
switch (vertexPosition) {
case V_LEFT_UP:
this->edges.push_back(EdgeB(i, 1, 1));
this->edges.push_back(EdgeB(i, 13, 1));
this->edges.push_back(EdgeB(i, 14, 1));
break;
case V_RIGHT_UP:
this->edges.push_back(EdgeB(i, 11, 1));
this->edges.push_back(EdgeB(i, 24, 1));
this->edges.push_back(EdgeB(i, 25, 1));
break;
case V_LEFT_DOWN:
this->edges.push_back(EdgeB(i, 143, 1));
this->edges.push_back(EdgeB(i, 144, 1));
this->edges.push_back(EdgeB(i, 157, 1));
break;
case V_RIGHT_DOWN:
this->edges.push_back(EdgeB(i, 154, 1));
this->edges.push_back(EdgeB(i, 155, 1));
this->edges.push_back(EdgeB(i, 167, 1));
break;
case V_UP_BORDER:
this->edges.push_back(EdgeB(i, i - 1, 1));
this->edges.push_back(EdgeB(i, i + 1, 1));
this->edges.push_back(EdgeB(i, i + 12, 1));
this->edges.push_back(EdgeB(i, i + 13, 1));
this->edges.push_back(EdgeB(i, i + 14, 1));
break;
case V_DOWN_BORDER:
this->edges.push_back(EdgeB(i, i - 1, 1));
this->edges.push_back(EdgeB(i, i + 1, 1));
this->edges.push_back(EdgeB(i, i - 12, 1));
this->edges.push_back(EdgeB(i, i - 13, 1));
this->edges.push_back(EdgeB(i, i - 14, 1));
break;
case V_LEFT_BORDER:
this->edges.push_back(EdgeB(i, i - 13, 1));
this->edges.push_back(EdgeB(i, i + 13, 1));
this->edges.push_back(EdgeB(i, i + 14, 1));
this->edges.push_back(EdgeB(i, i - 12, 1));
this->edges.push_back(EdgeB(i, i + 1, 1));
break;
case V_RIGHT_BORDER:
this->edges.push_back(EdgeB(i, i - 13, 1));
this->edges.push_back(EdgeB(i, i + 13, 1));
this->edges.push_back(EdgeB(i, i + 12, 1));
this->edges.push_back(EdgeB(i, i - 14, 1));
this->edges.push_back(EdgeB(i, i - 1, 1));
break;
case INNER:
this->edges.push_back(EdgeB(i, i + 1, 1));
this->edges.push_back(EdgeB(i, i - 1, 1));
this->edges.push_back(EdgeB(i, i + 13, 1));
this->edges.push_back(EdgeB(i, i - 13, 1));
this->edges.push_back(EdgeB(i, i - 14, 1));
this->edges.push_back(EdgeB(i, i - 12, 1));
this->edges.push_back(EdgeB(i, i + 14, 1));
this->edges.push_back(EdgeB(i, i + 12, 1));
break;
}
vertexPosition = INNER;
}
}
Again, it’s up to you to modify the code above to improve readability and maintainability according to your needs.
Like the article ? Share it ! ;)
