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:

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. 

bellman-ford-screenshot​​

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


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


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