Dijkstra's Algorithm: Shortest Paths for Weighted Graph

mgcadmin 19-09-2021

In this article I show how to implement Dijkstra's algorithm to show the shortest route by train through several American cities.

Single Source Shortest Path

Today we're going to take a look at another Single Source Shortest Path(SSSP) algorithm: Dijkstra's Algorithm. Edsgar Dijkstra invented this algorithm in the late 1950's in order to find the shortest flights between cities in Europe. It's been inferred that this algorithm, or a variation of it is what powers many common driving directions programs like google maps, and other GPS direction finders. It is also extremely popular in Robotics for route planning and obstacle avoidance, and in the video game development field for NPC pathfinding.

Relationship to other Algorithms

Dijkstra's Algorithm is very similar to other commonly used graphing algorithm. One in particular, Prims Minimum Spanning Tree Algorithm functions almost identically, except it builds a shortest path including all of the vertexes in the graph. A* search is an outgrowth of Dijkstra's Algorithm which incorporates a "heuristic" which guides the algorithm towards a possibly even better solution. All of these algorithms can be viewed as adaptations of Best First Search, sometimes called Priority First Search. In artificial intelligence it is sometimes called "Uniform Cost Search."

Priority Queues

When we implemented Breadth First Search we were able to get away with using a regular First In First Out queue. For this Algorithm we need to use a priority queue. a priority queue organizes output based on a weighted rank. Priority Queues can be implemented using a variety of data structures, the most common of which is a heap. 

One of the simplest ways to implement a priority queue is via a sorted linked list. Keep in mind that the choice of data structure for both the adjacency list, and the priority queue can have a very big impact on the running time of this algorithm. The fastest known implementation was discovered by Tarjan et. al. in the 1980s and incorporates a Fibonacci Heap.

Priority Queues can either be "Min Priority" or "Max Priority" depending on if the application at hand considers a higher value or lower value a better priority. For our purposes we will be using a min priority queue.

Where a normal queue only has two main operations, push() and pop(), our priority queue includes a third operation: update() which is used to change the priority of items already in the queue. 

Because this is an article on Dijkstras Algorithm, and not Priority Queues, i'm not going to go into the implementation details of my priority queue. The code for the priority queue used in this example is available on my github at:

https://github.com/maxgoren/examples/blob/main/priority_queue.h

The Graph

One of the input's to our algorithm is of course, the graph. I went over the implementation details of using the Standard Template Library for representing graphs in a previous article. I've expanded upon that implementation here. Were using strings for vertex labels, and were also keeping a list of all vertex names alongside our edge list, and lastly, i'm using a struct for representing edges instead of std::pair in the adjacency list. All of these changes lend to both a cleaner looking code, and a nicer looking graph and algorithm output. Lets take a look at the improved graph class:

#include <iostream>
#include <list>
#include <map>
using namespace std;

class Graph {
  public:
  typedef struct _edge {
     string vertex;
     int weight;
     _edge(string v, int w) : vertex(v), weight(w) { }
  } edge;
  string graphName;
  list<string> verts;
  map<string, list<edge> > adjList;
  void addEdge(string v, string u, int w);
  void showAdjList();
  bool findVert(string v);
  Graph(string N) : graphName(N) { }
};

bool Graph::findVert(string v)
{
  for (auto vert : verts)
  {
    if (vert == v)
     return true;
  }
  return false;
}

void Graph::addEdge(string v, string u, int w)
{
  if (!findVert(v))
    verts.push_back(v);
  if (!findVert(u))
    verts.push_back(u);
  adjList[v].push_back(edge(u, w));
  adjList[u].push_back(edge(v, w));
}

void Graph::showAdjList()
{
  cout<<graphName<<endl;
  verts.sort();
  for (auto vert : verts)
  {
   cout<<vert<<": ";
   for (auto adj : adjList[vert])
   {
     cout<<adj.vertex<<", ";
   }
   cout<<"\b\b\n";
  }
}

Overall not too much different from the implementation covered in my other graphing articles. findVert() is a simple sequential search of the vertex list, a feature i still think should be included in the STL list API. 

Dijkstra's Algorithm

With our priority queue and graph in place, we're ready to tackle the implementation of Dijkstra's Algorithm. One of the features of Dijkstra's Algorithm that sets it apart from both Depth First and Breadth First Search is that in this case we DO allow multiple visits to a vertex that we've already seen, in fact these multiple visits are the crux of how this algorithm works. If we find that by going through a vertex to a vertex we've already been to lowers the cost of travel to that vertex thus far, then we have essentially found a "short cut" on our shortest path and thus will want to incorporate it in said path. If we didnt allow visits to vertexes we've already visited, we wouldnt be able to do this. So instead of using an std::map<vertex, bool> for tracking visitation, we will use a std::map<vertex, int> for tracking distance. Initially we, are going to set the distance for each vertex to an arbitrarily high value, in our case INT_MAX. Aside from these changes, things progress very similarly to a normal Breadth First Search:

void dijkstraShortestPath(Graph& G, string v, string u)
{
   bool found = false;
   map<string, int> dist;        //Distance so far for each vertex
   map<string, string> camefrom; //previous vertex
   pq<string> s;                 //priority queue
   for (auto l : G.verts)
   {
     dist[l] = INT_MAX;
   }
   string current = v;
   s.push(current, 0);
   dist[current] = 0;
   camefrom[current] = current;
  while (!s.empty())
  {
    current = s.pop();
    cout<<"Current: "<<current<<endl;;
   if (current == u)
   {
     cout<<"Found!\n";
     found = true;
     break;
   }
   for (auto child : G.adjList[current])
   {
     if (dist[child.vertex] > dist[current] + child.weight)
     {
       dist[child.vertex] = dist[current] + child.weight;
       s.update(child.vertex, dist[child.vertex]);
       camefrom[child.vertex] = current;
     }
   }
  }
  cout<<"Search Over.\n";
  if (found)
  {
    cout<<"A Path Exists...\n";
    showPath(camefrom, dist, v, u);
   }
}

We also need a function for recreating the path taken:

void showPath(std::map<string, string> camefrom, std::map<string, int> dist, string v, string u)
{
  list<string> path;
  int pathdist = 0;;
  string crawl = u;
  path.push_back(crawl + "(" + to_string(dist[crawl]) + " hours)");
  while (crawl != v)
  {
    crawl = camefrom[crawl];
    path.push_back(crawl + "(" + to_string(dist[crawl]) + " hours)");
  }
  reverse(path.begin(), path.end());
  cout<<"Travel Time: "<<dist[u]<<" hours."<<endl;
  cout<<"Path: \n";
  for (auto p : path)
    cout<<p<<endl;
  cout<<endl;
}

Now its time to test our work, i decided to use train travel between U.S. Cities to see if our algorithm would give us real world results. Lets see how we did:

Driver program to build input graph:

int main(int argc, char *argv[])
{
  Graph G("United States Inter-City Passenger Rail Road");
  G.addEdge("New York", "Philidelphia", 2);
  G.addEdge("New York", "Boston", 2);
  G.addEdge("New York", "Washington D.C.", 4);
  G.addEdge("Philidelphia", "Washington D.C.", 2);
  G.addEdge("Washington D.C.", "Chicago", 18);
  G.addEdge("Washington D.C.", "Atlanta", 8);
  G.addEdge("Chicago", "Atlanta", 15);
  G.addEdge("Chicago", "Denver", 13);
  G.addEdge("Chicago", "New Orleans", 16);
  G.addEdge("New Orleans", "Houston", 11);
  G.addEdge("Denver", "Los Angeles", 20);
  G.addEdge("Houston", "Los Angeles", 22);
  G.addEdge("Los Angeles", "San Francisco", 8);
  G.addEdge("San Francisco", "Denver", 19);
  cout<<"\nDijkstras Algorithm: \n";
  dijkstraShortestPath(G, "New York", "New Orleans");
  return 0;
}

Dijkstras Algorithm: 
Current: New York
Current: Philidelphia
Current: Washington D.C.
Current: Atlanta
Current: Chicago
Current: Denver
Current: New Orleans
Found!
Search Over.
A Path Exists...
Travel Time: 38 hours.
Path: 
New York(0 hours)
Washington D.C.(4 hours)
Chicago(22 hours)
New Orleans(38 hours)

As you can see by the output from the algorithm, two things are clear: It gives us a very realistic/accurate route and travel time, importantly, the route given makes sense. It the algorithm considers routing our train from D.C. to Atlanta, but decided that D.C. to chicago was the better choice. Why? Because D.C. -> Chicago -> New Orleans was faster than D.C. -> Atlanta -> New Orleans! Nicely Done.

In this implementation we included a test for determining if we've reached our goal city or not. This is called the "Early Exit" technique. This test can be removed to yield whats called the Single Source All Paths variant.

Dijkstra's Algorithm is a powerful and useful algorithm, and its another tool we can now add to our tool box.

The full code for the examples shown at this website can be found on my github:

https://github.com/maxgoren/examples/blob/main/dijkstra.cpp

https://github.com/maxgoren/examples/blob/main/priority_queue.h

https://github.com/maxgoren/examples/blob/main/better-graph.h

For a full implementation of both BFS and Dijkstras SPA in C:

https://github.com/maxgoren/graph-algos/tree/main/Graphs-in-C

---