08 Jul 2020

Of Dijkstra and Priority Queues

Although I’ve implemented variants of Dijkstra’s algorithm in the past, I wanted to implement the algorithm using my own implementation of the priority queue. So, today I bring to you a reinvention of the wheel.

Especially when the project is small, I tend to develop software in Python and then translate the code into another language. Python is a clean, easy-to-use language that has a REPL. Consequently, it is quick and fun to develop in Python. Oftentimes there’s a better tool for the job, but I like to use Python when I can.

In this case, I implemented Dijkstra’s algorithm and the priority queue in Python and then translated the code into Java. So, I have:

One of the many interesting things that I learned from my artificial intelligence class is that the big difference between breadth-first search, depth-first search, and Dijkstra’s algorithm is the data structure that stores the vertices.

-In breadth-first search, the data structure is a queue. The first item that you put into it is the first item that you remove from it.

-In depth-first search, the data structure is a stack. The last item that you put into it is the first item that you remove from it.

-In Dijkstra’s algorithm, the data structure is a priority queue. The item that has the highest priority is the item that gets removed.

You can actually think of stacks and queues as types of priority queues. A queue is a priority queue where elements have more precedence the earlier they enter the container. A stack is a priority queue where elements have more precedence the later they enter the container.

Priority queues are commonly implemented as binary heaps, and that is how I implemented my priority queue. A binary heap is a complete binary tree that is ordered such that, for any given vertex, all of the vertex’s children have lower priority than it.

Dijkstra’s algorithm solves the single-source shortest path problem. In the single-source shortest path problem, you are given a graph and some distinguished vertex, and you want to find the shortest paths between the distinguished vertex and every other vertex in the graph. So, for example, let’s say that you are in Atlanta, and you want to find the quickest routes to Dallas, Chicago, and New York. Represent the highway system as a graph, and then you can apply Dijkstra’s algorithm to solve your problem.

At this page, I found “a data file that represents a significant portion of the interstate highway system”. So, I decided to actually compute the shortest paths from Atlanta to Dallas, Chicago, and New York. Here are the results:

The shortest distance between Atlanta and New York is 897 miles. The route is Atlanta -> Spartanburg -> Charlotte -> Greensboro -> Petersburg -> Richmond -> Washington -> Baltimore -> Philadelphia -> Newark -> New York.
The shortest distance between Atlanta and Dallas is 791 miles. The route is Atlanta -> Birmingham -> Meridian -> Jackson -> Shreveport -> Dallas.
The shortest distance between Atlanta and Chicago is 729 miles. The route is Atlanta -> Chattanooga -> Wildwood -> Nashville -> Louisville -> Indianapolis -> Gary -> Chicago.

Of course, the quality of these results depends on the quality of the data and the quality of the program that operates on the data. However, these results are close to the results that Google turns up. So, both the data and my implementation of Dijkstra’s algorithm seem to be good.

For more of my programs, check out my GitHub.