This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.

This algorithm is often used in routing and as a subroutine in other graph algorithms.



For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.



For instance

If the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road,   Dijkstra's algorithm can be used to find the shortest route between one city and all other cities.

As a result, the shortest path first is widely used in network routing protocols, most notably:

   IS-IS   (Intermediate System to Intermediate System)   and 
   OSPF   (Open Shortest Path First).


Important note
 
The inputs to Dijkstra's algorithm are a directed and weighted graph consisting of 2 or more nodes, generally represented by:

   an adjacency matrix or list,   and
   a start node. 


A destination node is not specified.

The output is a set of edges depicting the shortest path to each destination node.



An example, starting with

                                         a──►b,  cost=7,   lastNode=a  
                                         a──►c,  cost=9,   lastNode=a 
                                         a──►d,  cost=NA,  lastNode=a
                                         a──►e,  cost=NA,  lastNode=a 
                                         a──►f,  cost=14,  lastNode=a
 
    The lowest cost is    a──►b    so    a──►b    is added to the output. 
 
    There is a connection from   b──►d   so the input is updated to: 
                                         a──►c,  cost=9,   lastNode=a 
                                         a──►d,  cost=22,  lastNode=b 
                                         a──►e,  cost=NA,  lastNode=a 
                                         a──►f,  cost=14,  lastNode=a
 
    The lowest cost is    a──►c    so    a──►c    is added to the output. 
 
    Paths to    d    and    f    are cheaper via    c    so the input is updated to:
                                         a──►d,  cost=20,  lastNode=c 
                                         a──►e,  cost=NA,  lastNode=a 
                                         a──►f,  cost=11,  lastNode=c
 
    The lowest cost is    a──►f    so    c──►f    is added to the output. 
 
    The input is updated to:
                                         a──►d,  cost=20,  lastNode=c 
                                         a──►e,  cost=NA,  lastNode=a
 
    The lowest cost is    a──►d    so    c──►d    is added to the output. 
 
    There is a connection from    d──►e    so the input is updated to:
                                         a──►e,  cost=26,  lastNode=d
 
    Which just leaves adding    d──►e    to the output.
 
    The output should now be:
                                       [ d──►e
                                         c──►d
                                         c──►f
                                         a──►c
                                         a──►b ]   


Task

 Implement a version of Dijkstra's algorithm that outputs a set of edges depicting the shortest path to each reachable node from an origin.
 Run your program with the following directed graph starting at node    a.
 Write a program which interprets the output from the above and use it to output the shortest path from node    a    to nodes    e    and  f. 

 Vertices


 Number 
 Name


 1 
 a


 2 
 b


 3 
 c


 4 
 d


 5 
 e


 6 
 f


 Edges


 Start 
 End 
 Cost


 a 
 b 
 7


 a 
 c 
 9


 a 
 f 
 14


 b 
 c 
 10


 b 
 d 
 15


 c 
 d 
 11


 c 
 f 
 2


 d 
 e 
 6


 e 
 f 
 9



You can use numbers or names to identify vertices in your program.



See also
 Dijkstra's Algorithm vs. A* Search vs. Concurrent Dijkstra's Algorithm (youtube)


 
(declare neighbours
         process-neighbour
         prepare-costs
         get-next-node
         unwind-path
         all-shortest-paths)
 
 
;; Main algorithm
 
 
(defn dijkstra
  "Given two nodes A and B, and graph, finds shortest path from point A to point B.
  Given one node and graph, finds all shortest paths to all other nodes.
 
  Graph example: {1 {2 7 3 9 6 14}
                  2 {1 7 3 10 4 15}
                  3 {1 9 2 10 4 11 6 2}
                  4 {2 15 3 11 5 6}
                  5 {6 9 4 6}
                  6 {1 14 3 2 5 9}}
                  ^  ^  ^
                  |  |  |
         node label  |  |
    neighbour label---  |
          edge cost------
  From example in Wikipedia: https://en.wikipedia.org/wiki/Dijkstra's_algorithm
 
  Output example: [20 [1 3 6 5]]
                   ^  ^
                   |  |
  shortest path cost  |
       shortest path---"
  ([a b graph]
   (loop [costs (prepare-costs a graph)
          unvisited (set (keys graph))]
     (let [current-node (get-next-node costs unvisited)
           current-cost (first (costs current-node))]
       (cond (nil? current-node)
             (all-shortest-paths a costs)
 
             (= current-node b)
             [current-cost (unwind-path a b costs)]
 
             :else
             (recur (reduce (partial process-neighbour
                                     current-node
                                     current-cost)
                            costs
                            (filter (comp unvisited first)
                                    (neighbours current-node graph costs)))
                    (disj unvisited current-node))))))
  ([a graph] (dijkstra a nil graph)))
 
 
;; Implementation details
 
 
(defn prepare-costs
  "For given start node A ang graph prepare map of costs to start with
  (assign maximum value for all nodes and zero for starting one).
  Also save info about most advantageous parent.
  Example output: {2 [2147483647 7], 6 [2147483647 14]}
                   ^   ^         ^
                   |   |         |
                node   |         |
               cost-----         |
             parent---------------"
  [start graph]
  (assoc (zipmap (keys graph)
                 (repeat [Integer/MAX_VALUE nil]))
         start [0 start]))
 
 
(defn neighbours
  "Get given node's neighbours along with their own costs and costs of corresponding edges.
  Example output is: {1 [7 10] 2 [4 15]}
                      ^  ^  ^
                      |  |  |
   neighbour node label  |  |
        neighbour cost ---  |
             edge cost ------"  
  [node graph costs]
  (->> (graph node)
       (map (fn [[neighbour edge-cost]]
              [neighbour [(first (costs neighbour)) edge-cost]]))
       (into {})))
 
 
(defn process-neighbour
  [parent
   parent-cost
   costs
   [neighbour [old-cost edge-cost]]]
  (let [new-cost (+ parent-cost edge-cost)]
    (if (< new-cost old-cost)
      (assoc costs
             neighbour
             [new-cost parent])
      costs)))
 
 
(defn get-next-node [costs unvisited]
  (->> costs
       (filter (comp unvisited first))
       (sort-by (comp first second))
       ffirst))
 
 
(defn unwind-path
  "Restore path from A to B based on costs data"
  [a b costs]
  (letfn [(f [a b costs]
            (when-not (= a b)
              (cons b (f a (second (costs b)) costs))))]
    (cons a (reverse (f a b costs)))))
 
 
(defn all-shortest-paths
  "Get shortest paths for all nodes, along with their costs"
  [start costs]
  (let [paths (->> (keys costs)
                   (remove #{start})
                   (map (fn [n] [n (unwind-path start n costs)])))]
    (into (hash-map)
          (map (fn [[n p]]
                 [n [(first (costs n)) p]])
               paths))))
 
 
;; Utils
 
 
(require '[clojure.pprint :refer [print-table]])
 
 
(defn print-solution [solution]
  (print-table
   (map (fn [[node [cost path]]]
          {'node node 'cost cost 'path path})
        solution)))
 
 
;; Solutions
 
 
;; Task 1. Implement a version of Dijkstra's algorithm that outputs a set of edges depicting the shortest path to each reachable node from an origin.
 
;; see above
 
 
;; Task 2. Run your program with the following directed graph starting at node a.
 
;; Edges   
;;   Start    End  Cost     
;;   a        b    7     
;;   a        c    9     
;;   a        f    14     
;;   b        c    10     
;;   b        d    15     
;;   c        d    11     
;;   c        f    2     
;;   d        e    6     
;;   e        f    9     
 
(def rosetta-graph
  '{a {b 7 c 9 f 14}
    b {c 10 d 15}
    c {d 11 f 2}
    d {e 6}
    e {f 9}
    f {}})
 
(def task-2-solution
  (dijkstra 'a rosetta-graph))
 
(print-solution task-2-solution)
 
;; Output:
;; | node | cost |      path |
;; |------+------+-----------|
;; |    b |    7 |     (a b) |
;; |    c |    9 |     (a c) |
;; |    d |   20 |   (a c d) |
;; |    e |   26 | (a c d e) |
;; |    f |   11 |   (a c f) |
 
 
;; Task 3. Write a program which interprets the output from the above and use it to output the shortest path from node a to nodes e and f
 
(print-solution (select-keys task-2-solution '[e f]))
 
;; Output:
;; | node | cost |      path |
;; |------+------+-----------|
;; |    e |   26 | (a c d e) |
;; |    f |   11 |   (a c f) |
 