Dijkstra the short and greedy!

Dijkstra’s algorithm is one of many algorithm to find the shortest path from a source node to all other nodes on a graph. While it is not the fastest algorithm out there, it is one of the most documented and easiest to implement. It behaves like the breadth-first search algorithm in that it expands its search until it has exhausted the whole graph and ultimately found the shortest path from the source to all other nodes. Likewise it shows its greediness by selecting the lowest cost node known for each iteration. This means that it might expand one path, then jump back to a previous path which is now the current cheapest path and so on.

Properties of Dijkstra:

  • There can not be any negative cycles in the graph. 
  • There can not be any negative weighted edges.
  • Does not inherently produce paths
  • Can be turned into a all-pair-shortest-path (apsp) algorithm by running Dijkstra once from every node.

Here is a dataset taken from “Adjacency Matrices in Dijkstra’s Shortest Path Algorithm”(J. Rhodes, 2012), which presumably represents a fictitious cost’s of travelling between different cities. The data is laid out as it would be represented in an adjacency matrix.

fromExcel01

And here is a not so elegant visualisation of the graph!

testDataSet01_10

Dijkstra does not inherently provide the shortest path found, just the cheapest travel cost. But one can implement a parent system where you can deduct the path from a target to the source. By running Dijkstra from Paris with a parent system we can see how much it costs to travel to each city and what path is the cheapest one.

Barcelona   Costs: 1080     Paris -> Geneve -> Narbonne -> Barcelona
Geneve      Costs: 540      Paris -> Geneve
Lausanne    Costs: 536      Paris -> Lausanne
London      Costs: 440      Paris -> London
Marseille   Costs: 800      Paris -> Geneve -> Marseille
Narbonne    Costs: 830      Paris -> Geneve -> Narbonne
Oxford      Costs: 535      Paris -> London -> Oxford
Paris       Costs: 0        Paris ->
Toulouse    Costs: 680      Paris -> Toulouse

Done with the boring dataset! The whole reason of looking into Dijkstra is to apply it for mesh segmentation, so here is the behaviour of Dijkstra’s algorithm visualised on different meshes.

Here is a implementation of Dijkstra with parent system to illustrate the resulting paths.