Home > Algorithms, C/C++ > Dijkstra’s Algorithm – Solving the Shortest Path Problem

Dijkstra’s Algorithm – Solving the Shortest Path Problem

August 20th, 2013 Leave a comment Go to comments

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:

 

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. 

kosta-hristov-bachelor-work​​

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. 

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:

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

DijkstraImplementation.cpp

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:

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. 


 

 


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. September 1st, 2013 at 13:55 | #1

    Great post. One of my favourite algorithms. I did one in c# for level generation in a game not too long ago:
    http://www.arakawa.asia/graphs-and-pathing-in-csharp/

  2. September 2nd, 2013 at 10:53 | #2

    Yes, it's good. :) Also the Bellman Ford's algorithm is great in case negative edges are present. 

  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.