A C implementation of Dijkstra algorithm

Introduction

Dijkstra algorithm is a very famous computer-science algorithm to find shortest-path in graphs. It is for example used in the "open shortest path first" protocol for IP routing, and also in many other graphs&networks applications. It can also be used with IA applications to find the shortest-path to move a character from a place to another.

Described here is a C implementation of this algorithm applied to images. The graph is therefore much less general, and can be reduced to a simpler case where each vertex (pixel) is linked only to its direct geographic neighbours. For each vertex, we have several edges to reach its neighbours, and for each edge is associated a cost. That cost describes how easy it is to go from vertex i to vertex j.

A more intuitive representation would be to imagine a grid for a 3D mesh, where the cost to move from a place to another would represent the altitude which we have to climb to reach the destination point.

We are interested in finding the shortest-path from a starting point to a destination point only. The algorithm is also able to extract the shortest-path to all visited vertices. This data is available in our implementation, but is not what we aim at doing.




Complexity



As you can imagine, the algorithme will take some times when ran on huge grids. Indeed, Dijkstra algorithm runs in O(|E+V| log |V|) time with a standart implementation. (E number of edges, V number of vertices).
Moreover, working on images implies that the number of pixels (vertices) will grow like the square of the image's width.
Some applications require working on high resolution pictures with a reasonable computation time. We come here with a trade-off allowing fast shortest-path computation, which of course does not guarantee to give the shortest-path. Hopefully, it provides a "good-enough" path, which can be satisfying for many applications.




Implementation



Two main steps are necessary to compute a shortest-path:


    

  1. Building a graph out of an image
    2. 

  2. Finding the shortest-path from that graph
    3. 




As you can imagine, building the graph can be done in O(n) time (with n the number of pixels of the image). Unfortunately, multiplying the image width by two will multiply the number of pixels (and the graph-creation) by 4.
Also, the shortest-path finding will take some times for huge images.




Now, we need to compute the shortest-path itself. Here is how we proceed:




Computing the shortest-path at two different resolutions


    

  • Compute the shortest-path for another image with a lower resolution (typically with 4 times less pixels).
    • 

  • Select an area around that shortest-path, and fit it to the high-resolution image. Create a new graph containing the pixels of this image, taking into account only the ones which are inside the area we selected. Compute Dijkstra algorithm in that area.
    • 




This way, a lot of memory is saved, and the path's computation time remains low.
Multi-res_scale
The graph building time is certainly the slowest operation of the process. But once it is done, you can compute as many shortest path as you want pretty quickly.




Applications



Initally, this code was developed to follow arteries and veins in retinographies. But there must be many other applications to that algorithm. Here is for example a maze resolved by Dijkstra's algorithm:
Dijkstra_maze




Getting the code



The code can be downloaded from the Bitbucket repository.




Python module



The above code contains a python module. it needs to be compiled using
python setup.py build
and as root, will install using:
python setup.py install