Experimenting with Dijkstra’s algorithm

This little project aims to measure the performance of different implementation of one of the most known single source shortest path algorithm, Dijkstra’s shortest path algorithm. I am considering the naive, priority queue with binary heap and priority queue with Fibonacci heap type implementations where I am using existing open-source implementation of the Fibonacci heap. My goal with this experiment is to show different implementation’s strength and also to investigate the performance of existing open-source Fibonacci heap implementations. All the theoretical knowledge can be found in CLRS 24.3 and CLRS 19. To get deeper understanding on the measurement, I have decided to split the text into 4 parts:

• All about Dijkstra’s algorithm
• Implementation details
• Data generation and measurement scenarios
• Results

All the code mentioned in this article is available on GitHub. Feel free to check it out and comment it. https://github.com/gabormakrai/dijkstra-performance

Dijkstra’s algorithm

Dijkstra’s shortest path algorithm is a single source shortest path algorithm. It is calculating all shortest paths from single source point/vertex/node. The algorithm itself is creating a shortest path spanning tree which is always stored in a vector, called the previous vector. This vector helps us to create the actual shortest path from the origin to the target by stepping back on this vector. For more details, see CLRS 24.3.

All the different versions of Dijkstra’s algorithm differ in the way they are creating the previous vector. The first naive implementation’s pseudo code is the following: (I have used here the pseudocode from Wikipedia, because it is easy to understand)

function Dijkstra(Graph, source):
  dist  := 0                  // Distance from source to source
  prev  := undefined          // Previous node in optimal path initialization

  for each vertex v in Graph:         // Initializations
    if v ≠ source                     // Where v has not yet been removed from Q (unvisited nodes)
      dist[v]  := infinity            // Unknown distance function from source to v
      prev[v]  := undefined           // Previous node in optimal path from source
    end if 
    add v to Q                        // All nodes initially in Q (unvisited nodes)
  end for

  while Q is not empty:               // The main loop
    u := vertex in Q with min dist[u] // Source node in first case
    remove u from Q 

    for each neighbor v of u:         // where v has not yet been removed from Q.
      alt := dist[u] + length(u, v)
      if alt < dist[v]:            // A shorter path to v has been found
        dist[v]  := alt 
        prev[v]  := u 
      end if
    end for
  end while

  return dist[], prev[]

end function

This is going to be my first, naive implementation of the Dijkstra’s algorithm where I am using a simple full scan search for finding the closest vertex in the distance vector. This comes with O(n) time complexity so the overall time complexity is O(|E| + |V|²). It is clear that finding the closest vertex/node can be achieved by maintaining an advanced data structure to reduce the search time. Priority Queues can help in this, where the queue can be implemented as a binary heap reducing time complexity to O((|E|+|V|)log|V|) or a more advanced data structure developed specially for this algorithm, the Fibonacci heap where the time complexity can be reduced to O(|E| + |V|log|V|). The code for calculating the previous vector in general is the following:

function Dijkstra(Graph, source):
  dist := 0                 // Initializations
  for each vertex v in Graph:           
    if v ≠ source
      dist[v] := infinity           // Unknown distance from source to v
      previous[v] := undefined      // Predecessor of v
    end if
    Q.add_with_priority(v,dist[v])
  end for 

  while Q is not empty:             // The main loop
    u := Q.extract_min()            // Remove and return best vertex
    mark u as scanned
    
    for each neighbor v of u:
      if v is not yet scanned:
        alt = dist[u] + length(u, v) 
        if alt < dist[v]
          dist[v] := alt
          previous[v] := u
          Q.decrease_priority(v,alt)
        end if
      end if
    end for
  end while

  return previous[]
end function

Using Fibonacci heap for the Priority Queue can be decrease the running time, because it has θ(1) amortized cost on Decrease key and insert operations compared to the θ(lgn) Decrease key operation of binary heap. The following table is showing all the necessary operations for the Priority Queue implementation of both heap (CLRS 19.1):

Procedure	Binary heap	Fibonacci heap
MAKE-HEAP	θ(1)	θ(1)
INSERT	θ(lgn)	θ(1)
MINIMUM	θ(1)	θ(1)
EXTRACT-MIN	θ(lgn)	O(lgn)
DECREASE-KEY	θ(lgn)	θ(1)
DELETE	θ(lgn)	O(lgn)

The Fibonacci heap itself was developed based on the observation that usually there are multiple Decrease-Key operations related to one Extract-Min operation.

Implementation details

In this framework, there are a couple of different implementations of the algorithm, but they can be classified into three different groups:

• Naive implementation
• Binary Tree Priority Queue implementation
• Fibonacci Heap Priority Queue implementation

Before I introduce the implementation details of the algorithms, I will introduce how the framework is implementing the graph. I coded the neighbourhood list approach where two nested arrays represent the actual graph: there is a int[][] which is storing the neighbour nodes for each node and a double[][] which is storing the corresponding arc/edge weights.

Naive implementation

It is obviously the slowest version (algorithmically), however the results of this version can be useful for validating the other implementation correctness. Also it is interesting to see how this simple version is performing against other advanced implementation. The simplicity of this implementation is giving the chance to the Java VM to optimize the code and also it is giving the opportunity to the hardware architecture for low-level optimization (for example branch prediction).

The actual implementation can be found here: BaseDijsktra

Binary Tree Priority Queue implementation

As mentioned before, it is possible to use Priority Queues to speed up the algorithm. For this and the other Priority Queue style algorithms, I created a general code to test them. This version of the Dijkstra can be found here: PriorityQueueDijkstra For every single PriorityQueue algorithm, there is a wrapper class which is using the heap algorithm inside to represent the Priority Queue. The interface for it can be found here: PriorityQueue. There is a built-in binary search tree (TreeSet, which is based on TreeMap which is a red-back binary search tree) in Java and the framework uses this search tree for the Priority Queue.

Implementation of the TreeSet Priority Queue can be found here: TreeSetPriorityQueue

Fibonacci Heap Priority Queue implementation

Instead of trying to implement myself the Fibonacci heap, I tried to find existing open-source implementations. After reading through many pages of the Google search “Fibonacci heap Java” I could find the following ones:

• Teneigty’s implementation
• Neo4j’s implementation
• Pengyifan’s implementation
• GrowingTheWeb’s implementation
• Keithschwarz’s implementation
• Nutch’s implementation

As mentioned before, I created individual wrapper classes for the different implementation of Priority Queues:

• Teneigty’s wrapper
• Neo4j’s wrapper
• Pengyifan’s wrapper
• GrowingTheWeb’s wrapper
• Keithschwarz’s wrapper
• Nutch’s wrapper

Data generation and measurement scenarios

For the data generation, I have created a random graph generator. This generator created random directed graphs according the two parameters:

• size of the graph in the terms of vertices/nodes in the graph (parameter n)
• connectivity of the graph: how sparse is the graph (parameter p)
• the connectivity is expressed by a 0.0 <= p <= 1.0 floating number where 0.0 means there is no edge/arc in the graph and 1.0 means it is a complete graph

Here is just a simple example of the graph generation method with different connectivity parameter: (online version of the Graphviz) was used to generate these graph using the output of this simple program: GraphGeneratorDotOutputMain, Output text file)

n=10,p=0.1	n=10,p=0.3	n=10,p=0.5	n=10,p=0.9

The generation method has two phases:

• In the beginning, it is creating a random directed spanning tree to make sure that the graph is fully connected. (we can reach every node from other node)
• The second phase is the random arcs/edges addition phase, where random arcs/edges are added until the necessary connectivity rate has been reached

The framework implements measurement scenarios in the way that different algorithms can be compared to each other in the fairest way. We are only considering the calculation of the previous/distance vector, which is the core for the Dijkstra’s algorithm. For each experiment, the framework creates a random graph and runs 20 random vector generation from different origins. Only the runtime of the vector calculation is measured. This process is repeated 20 times and the 3 worst and best runtime has been dropped (to avoid outlier runtimes) and an average runtime is calculated from the remaining 14 runtimes.

Results

The computer and runtime environment which was executing the tests has the following properties:
* Intel Core i7-4770K CPU
* 32 GB memory
* Java 1.7.0_51 JDK
* Windows 7 64bit SP1 OS

As described before, the framework has different implementations of the Dijkstra’s algorithm:

• Naive implementation
• Priority Queue with the built-in TreeSet binary heap
• Priority Queue with Neo4j’s Fibonacci heap
• Priority Queue with Nutch’s Fibonacci heap
• Priority Queue with Teneighty’s Fibonacci heap
• Priority Queue with Keithschwarz’s Fibonacci heap
• Unfortunately there were two implementations of the Fibonacci heap which produced unexpected exceptions during the tests
  • Growing with the web’s Fibonacci heap
  • Pengyifan’s Fibonacci heap

For the first run, I was curious about the implementations’ runtime on different graph sizes. The framework was executing the following file to find the right answer: GraphSizeAnalysisMain. It is measuring the runtime depends on different sizes (from n = 10 to n = 1000 in steps of 10) and connectivity (from p = 0.1 to p = 0.9 in steps of 0.2). The following figures contain the results:

Test case with p = 0.1	Test case with p = 0.3	Test case with p = 0.5

Test case with p = 0.7	Test case with p = 0.9

The absolute winner was the Priority Queue version with Teneight’s Fibonacci heap and all Fibonacci heap Priority Queue implementation beats the other two. It is also interesting to see that in a spare graph, the naive implementation was overperformed by all the others implementation, but in a well connected graph, the naive implementation beats Priority Queue with binary heap implementation.