## Dijkstra

Debugs a buggy implementation of Dijkstra’s algorithm.

### `dijkstra/dijkstra.ss`

```(module dijkstra mzscheme
(require "dijkstra-solver.ss"
"graph.ss"
(lib "list.ss"))
(print-struct #t)
(define g (make-graph 'directed))
(define (m-node label x y) (make-node label x y +inf.0))
(define nodes
(list
(m-node 'J 200 100)
(m-node 's 100 125)
(m-node '1 150 100)
(m-node '2 150 150)
(m-node '4 250 100)
(m-node '5 300 100)
(m-node '6 300 150)))
(for-each (lambda (n) (graph-node-add! g n)) nodes)
(define (n-ref label)
(first (filter (lambda (n) (eq? label (node-label n))) nodes)))

(define edges
(list  (list (n-ref 's) (n-ref '1))
(list (n-ref 's) (n-ref '2))
(list (n-ref '1) (n-ref 'J))
(list (n-ref '4) (n-ref '5))
(list (n-ref 'J) (n-ref '4))
(list (n-ref 'J) (n-ref '6))))
(for-each (lambda (e) (graph-edge-add! g (first e) (second e)))
edges)

(printf "~n~n---output from dijkstra.ss:~n~a~n---~n"
(solve g (reverse nodes) (n-ref 's))))```

### `dijkstra/dijkstra-mztake.ss`

```(require "dijkstra-solver.ss"
(lib "match.ss"))

(define-mztake-process p
("dijkstra.ss")
("heap.ss" [inserts 49 6 bind 'item]
[removes 67 10 bind 'result]))

(define (not-in-order e)
(filter-e
(match-lambda
[('reset _) false]
[(_ 'reset) false]
[(previous current) (> previous current)]
[else false])
(history-e 2 e)))

(define inserts-and-removes-e (merge-e (removes . ==> . node-weight)
(inserts . -=> . 'reset)))
(define violations (not-in-order inserts-and-removes-e))

(printf-b "all inserts and removes: ~a" (history-b inserts-and-removes-e))
(printf-b "all violations: ~a" (history-b violations))
(printf-b "latest-violation: ~a" (hold violations))

#| Implementation of the local model follows... |#
(define ((insert-in-model item) model)
(printf "~nInserting ~a into model containing:~n~a~n" item (value-now model))
(cons item model))

(define ((remove-from-model item) model)
(printf "~nRemoving ~a from model containing:~n~a~n" item (value-now model))
(filter (lambda (i) (not (equal? i item))) model))

(define inserters (accum-b (inserts . ==> . insert-in-model) empty))
(define removers  (accum-b (removes . ==> . remove-from-model) inserters))

(start/resume p)```