• Tweet

• Tweet

Introduction

Finding the shortest path in a graph is a task seldom required by most of the programmers nowadays, because the exact implementation details are usually well hidden behind ready to use libraries and frameworks. Nonetheless, knowing your options when you are in front of such a problem is always a good thing, along with having a bit of a low level implementation at your disposal. 

In the following paragraphs, I will make a brief overview of one of the most famous algorithms for finding the shortest path – Dijkstra's algorithm​. I will also provide an example implementation for a board game. 

Algorithm overview

Dijkstra is an algorithm created by the Dutch computer scientist Edsger Djikstra in 1956 and published in 1959, designed to find the shortest path in a graph without negative edge path costs. For a given source vertex, the shortest path to any other vertex can be determined and tracked, producing a shortest path tree. It is used in a variety of network protocols including IS-IS and OSPF (Open Shortest Path First), which is an internal open standard link-state routing protocol.

​

Pseudocode

The following is a pseudocode for the Dijkstra’s algorithm:

function Dijkstra(Graph, source):
      for each vertex v in Graph:    // Initializations
          dist[v] := infinity ;      // Unknown distance function from 
                                     // source to v
          previous[v] := undefined ; // Previous node in optimal path
      end for                        // from source
      
      dist[source] := 0 ;            // Distance from source to source
      Q := the set of all nodes in Graph ; // All nodes in the graph are
                                    // unoptimized – thus are in Q
      while Q is not empty:         // The main loop
          u := vertex in Q with smallest distance in dist[] ;    // Source node in first case
          remove u from Q ;
          if dist[u] = infinity:
              break ;              // all remaining vertices are
          end if                   // inaccessible from source
          
          for each neighbor v of u: // where v has not yet been 
                                    // removed from Q.
              alt := dist[u] + dist_between(u, v) ;
              if alt < dist[v]:    // Relax (u,v,a)
                  dist[v] := alt ;
                  previous[v] := u ;
                  decrease-key v in Q;  // Reorder v in the Queue
              end if
          end for
      end while
      return dist;
  endfunction

Dijkstra’s algorithm – C++ implementation

Implementing a board game

What I will show you is an implementation of the Dijkstra's algorithm I am currently using for my bachelor's work. The project is a board-based simulation game with both manual and automatic control. For the simulation mode I use 3 types of tracking algorithms, the first one is Dijkstra, the second is BellmanFord, and the third one is a simple custom implementation I've created. 

​​

The idea of the game is that the wolves hunt everything they see, more or less. You can see the red dotted line, which is the actual path determined by the Djikstra's algorithm for the predator instinct. For the implementation I've modified an already existing version of the algorithm in order to fit my needs. 

    bool determinePath_Djikstra(qreal ax, qreal ay, qreal bx, qreal by, int &lastBestRange,
                                std::vector<vertex_t> &pathToTarget, int &direction);

This method takes x and y of the point of origin and the target vertex. The pathToTarget receives a vector of vertexes with the shortest path. The following is the code which uses the actual Dijkstra algorithm discussed in the next section:

bool WolfHuntAlgorithm::determinePath_Djikstra(qreal ax, qreal ay, qreal bx, 
qreal by, int &lastBestRange, std::vector<vertex_t> &pathToTarget, int &direction)
{
    int wolfVertex = ax/43 + (ay/43*13);
    int rabbitVertex = bx/43 + (by/43*13);
 
    std::map<vertex_t, weight_t> min_distance;
    std::map<vertex_t, vertex_t> previous;
 
    DijkstraComputePaths(wolfVertex, this->adjacency_map, min_distance, previous);
 
    pathToTarget = DijkstraGetShortestPathTo(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;
    }
 
    if(newBestRange < lastBestRange)
    {
        lastBestRange = newBestRange;
 
        return true;
    }
 
    return false;
}

Here 43 is the size of each cell. I have coordinates which have to be translated to vertex numbers. 

​The actual algorithm

The following is the actual implementation of the algorithm. 

DijkstraImplementation.h

typedef int vertex_t;
typedef double weight_t;
 
struct EdgeA {
    const vertex_t target;
    const weight_t weight;
    EdgeA(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }
};
 
typedef std::map<vertex_t, std::list<EdgeA> > adjacency_map_t;

DijkstraImplementation.cpp

void DijkstraComputePaths(vertex_t source,
                          const adjacency_map_t &adjacency_map,
                          std::map<vertex_t, weight_t> &min_distance,
                          std::map<vertex_t, vertex_t> &previous)
{
    for (adjacency_map_t::const_iterator vertex_iter = adjacency_map.begin();
         vertex_iter != adjacency_map.end();
         vertex_iter++)
    {
        vertex_t v = vertex_iter->first;
        min_distance[v] = std::numeric_limits< double >::infinity();
        for (std::list<EdgeA>::const_iterator EdgeA_iter = vertex_iter->second.begin();
             EdgeA_iter != vertex_iter->second.end();
             EdgeA_iter++)
        {
            vertex_t v2 = EdgeA_iter->target;
            min_distance[v2] = std::numeric_limits< double >::infinity();
        }
    }
 
    min_distance[source] = 0;
    std::set< std::pair<weight_t, vertex_t> > vertex_queue;
    vertex_queue.insert(std::make_pair(min_distance[source], source));
 
    while (!vertex_queue.empty())
    {
        vertex_t u = vertex_queue.begin()->second;
        vertex_queue.erase(vertex_queue.begin());
 
        // Visit each EdgeA exiting u
        const std::list<EdgeA> &EdgeAs = adjacency_map.find(u)->second;
        for (std::list<EdgeA>::const_iterator EdgeA_iter = EdgeAs.begin();
             EdgeA_iter != EdgeAs.end();
             EdgeA_iter++)
        {
            vertex_t v = EdgeA_iter->target;
            weight_t weight = EdgeA_iter->weight;
            weight_t distance_through_u = min_distance[u] + weight;
        if (distance_through_u < min_distance[v]) {
            vertex_queue.erase(std::make_pair(min_distance[v], v));
 
            min_distance[v] = distance_through_u;
            previous[v] = u;
            vertex_queue.insert(std::make_pair(min_distance[v], v));
        }
        }
    }
}
 
std::vector<vertex_t> DijkstraGetShortestPathTo(
    vertex_t target, const std::map<vertex_t, vertex_t> &previous)
{
    std::vector<vertex_t> path;
    std::map<vertex_t, vertex_t>::const_iterator prev;
    vertex_t vertex = target;
    path.insert(path.begin(), vertex);
    while((prev = previous.find(vertex)) != previous.end())
    {
        vertex = prev->second;
        path.insert(path.begin(), vertex);
    }
    return path;
}

The input/output parameters for DjikstraComputePaths are as follows :

• source – the source vertex
• adjacency_map – an adjacency matrix forming the actual graph. In this case, it is a simple rectangle. 
• min_distance – 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. 

The other part of the algorithm – the DjikstraGetShortestPathTo 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 DjikstraComputePaths function. 

​

Initializing the adjacency matrix

As you can see, this implementation works with an adjacency matrix. For my project I needed a graph to support a board game, but in your case this might be something else. Here is an example code for the matrix initialization in the case of a board game as a square:

void WolfHuntAlgorithm::initializeFieldGraph_Djikstra()
{
 
    VERTEX vertexPosition = INNER;
 
    for (int i = 0; i < 169; ++i) {
        this->vertex_names.push_back(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->adjacency_map[i].push_back(EdgeA(1,  1));
            this->adjacency_map[i].push_back(EdgeA(13,  1));
            this->adjacency_map[i].push_back(EdgeA(14,  1));
 
            break;
        case V_RIGHT_UP:
            this->adjacency_map[i].push_back(EdgeA(11,  1));
            this->adjacency_map[i].push_back(EdgeA(24,  1));
            this->adjacency_map[i].push_back(EdgeA(25,  1));
 
            break;
        case V_LEFT_DOWN:
            this->adjacency_map[i].push_back(EdgeA(143,  1));
            this->adjacency_map[i].push_back(EdgeA(144,  1));
            this->adjacency_map[i].push_back(EdgeA(157,  1));
 
            break;
        case V_RIGHT_DOWN:
            this->adjacency_map[i].push_back(EdgeA(154,  1));
            this->adjacency_map[i].push_back(EdgeA(155,  1));
            this->adjacency_map[i].push_back(EdgeA(167,  1));
 
            break;
        case V_UP_BORDER:
            this->adjacency_map[i].push_back(EdgeA(i - 1,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 1,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 12,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 14,  1));
 
            break;
        case V_DOWN_BORDER:
            this->adjacency_map[i].push_back(EdgeA(i - 1,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 1,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 12,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 14,  1));
 
            break;
        case V_LEFT_BORDER:
            this->adjacency_map[i].push_back(EdgeA(i - 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 14,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 12,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 1,  1));
 
            break;
        case V_RIGHT_BORDER:
            this->adjacency_map[i].push_back(EdgeA(i - 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 12,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 14,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 1,  1));
 
            break;
        case INNER:
            this->adjacency_map[i].push_back(EdgeA(i + 1,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 1,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 13,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 14,  1));
            this->adjacency_map[i].push_back(EdgeA(i - 12,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 14,  1));
            this->adjacency_map[i].push_back(EdgeA(i + 12,  1));
 
            break;
        }
 
        vertexPosition = INNER;
    }
}

As you can see, this is a quick way to initialize a square graph with 170 vertices as an adjacency matrix. The magic numbers could have been taken out into constants, but I'm sure you can catch on with that.