anchor.diff:  ; tests
   
   (set-graph '((a (b 3)) (b (c 1) (d 5)) (c (d 2)) (d (b 2))))
  -; (init-path-s graph)
  -; (update-path- 'a 0)
  -(dijkstra graph 'a)
  +(init-path-costs graph)
  +(update-path-cost 'a 0)
  +(print path-costs)
  +(init-predecessors graph)
  +(print predecessors)
  +(init-visited)
  +(print visited)
  +(init-candidates 'a)
  +(print candidates)
  +(path-cost 'a)
  +; (dijkstra graph 'a)
  
positive.code: ; Dijkstra's algorithm for finding the shortest path between nodes in a weighted graph
  
  (defun dijkstra (graph start)
    (init-path-costs graph)
    (update-path-cost start 0)
    (init-predecessors graph)
    (init-visited)
    (init-candidates start)
    (loop while candidates do
          (let ((current (min-candidate)))
            (add-visited current)
            (loop for neighbour in (set-difference (neighbours current) visited :test #'equal) do
                  (cond (< (+ (path-cost (name current)) 
                              (cost-to-neighbour neighbour))
                           (path-cost neighbour)) 
                        ((update-path-cost (name neighbour)
                                           (+ (path-cost (name current)) 
                                              (cost-to-neighbour neighbour)))
                         (update-predecessor (name neighbour)
                                             (name current)))
                        ((not (member (name neighbour) visited))
                         (add-visited (name neighbour)))))
            finally predecessors)))
  
  ; keep track of the smallest cost to get to each node found by dijkstra
  ; note that all paths start at the start node called in dijkstra
  (defun init-path-costs (graph)
    (let ((impossible (+ 1 (apply '+ (remove-if-not #'integerp (flatten graph))))))
      (setq path-path-costs (mapcar #'(lambda (node) (list node impossible)) (list-nodes graph)))))
  
  (defun flatten (llist)
    (cond ((null llist) nil)
  
negative.code:         (t (append (flatten (car llist)) (flatten (cdr llist))))))
  
  (defun update-path-cost (end path-cost)
    (setq path-costs 
          (append (remove-if #'(lambda (node) (equal (car node) end)) 
                             path-costs) 
                  (list (list end path-cost)))))
  
  ;;; takes the name of a node
  (defun path-cost (target)
    (cadar (remove-if-not #'(lambda (node) (equal (car node) target)) 
                          path-costs)))
  
  ;;; keep track of the predecessor of each node on the shortest path to the start node
  (defun init-predecessors (graph)
    (setq predecessors (mapcar #'(lambda (node) (list node nil)) 
                               (list-nodes graph))))
  
  ;;; end and predecessor are names of a nodes
  (defun update-predecessor (end predecessor)
    (setq predecessors (append (remove-if #'(lambda (node) (equal (car node) end))
                                          predecessors) 
                               (list (list end predecessor)))))
  
  (defun init-visited ()
    (setq visited nil))
  