Dijkstra's Algorithm
Write a function to calculate the shortest path between two nodes in a graph using Dijkstra's Algorithm. The graph is directional and is represented as a map. The keys are pairs of nodes and the value is the cost to traverse the edge between them, from the first node to the second node. If a pair of nodes does not exist in the map, it means that there is no edge between them.
Example graph
(def graph {[:a :b] 1
[:a :c] 2
[:c :a] 4})
Your function should return a path, consisting of a sequence of the names of the nodes to follow, including the starting end ending nodes.
Example
(shortest-path graph :c :b) ;=> [:c :a :b]
(shortest-path graph :a :a) ;=> [:a]
(shortest-path graph :a :b) ;=> [:a :b]
(shortest-path graph :b :c) ;=> nil (because no path exists)
For a description of the algorithm, see the wikipedia page or any textbook on algorithms.
Please submit your solutions as comments on this gist.
To subscribe: https://purelyfunctional.tv/newsletter/
I convert the original "graph" input into a nested map. The
cost-map
is a map of a terminal node key to a vector path of nodes + cost. So the cost is accessed withpeek
, and the path is accessed withpop
. I also keep the unvisited nodes (a set) under a special::unvisited
key in the samecost-map
. A more conventional Clojure approach might use a more nested structure with explicit keys for the different kinds of information. Example of mycost-map
state:{:b [:c :b 5] :c [:c 0] ::unvisited #{:a :b :d}}
.I was partially inspired by this blog post: http://loganlinn.com/blog/2013/04/22/dijkstras-algorithm-in-clojure/ But I have made a lot of changes so any bugs are my fault.