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.
And here is a not so elegant visualisation of the graph!
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.