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/
In case that is useful to others, here is the wikipedia example, which is both non-trivial and easy to verify visually: