Version: 4.1.5.5

## Dijkstra’s Algorithm

 (require (planet jaymccarthy/dijkstra:1:2))

This package provides an implementation of Dijkstra’s Algorithm that uses a Fibonacci heap for the queue.

(shortest-path node-edges
edge-weight
edge-next
start
[stop?])
 hash? hash?
node-edges : (any/c . -> . (listof any/c))
edge-weight : (any/c . -> . number?)
edge-next : (any/c . -> . node?)
start : any/c
stop? : (any/c . -> . boolean?) = (lambda (n) #f)

Starts the algorithm at start using node-edges to determine a node’s edges edge-weight to find the weight of the edge and edge-next to find the node at the end of an edge. The search is stopped if stop? returns #t on the minimum element in the queue (so you can pass (lambda (n) (= n target)) to have a directed search.)

The return values are first a hash table mapping nodes to their distance from start and second a hash table mapping nodes to the previous node on the shortest path.

 (shortest-path-to previous target) → (listof node?) previous : hash? target : any/c

Uses previous (the second return value from shortest-path) to trace a path from the start to target.

### 1Example

 (define-struct edge (end weight)) (define-struct graph (adj)) (define (create-graph) (make-graph (make-hasheq))) (define (graph-add! g start end [weight 0]) (hash-update! (graph-adj g) start (lambda (old) (list* (make-edge end weight) old)) empty)) (define (graph-shortest-path g src [stop? (lambda (n) #f)]) (shortest-path (lambda (n) (hash-ref (graph-adj g) n empty)) edge-weight edge-end src stop?)) (define g (create-graph))

> (graph-add! g 1 2 4)
> (graph-add! g 1 4 1)
> (graph-add! g 2 1 74)
> (graph-add! g 2 3 2)
> (graph-add! g 2 5 12)
> (graph-add! g 3 2 12)
> (graph-add! g 3 10 12)
> (graph-add! g 3 6 74)
> (graph-add! g 4 7 22)
> (graph-add! g 4 5 32)
> (graph-add! g 5 8 33)
> (graph-add! g 5 4 66)
> (graph-add! g 5 6 76)
> (graph-add! g 6 10 21)
> (graph-add! g 6 9 11)
> (graph-add! g 7 3 12)
> (graph-add! g 7 8 10)
> (graph-add! g 8 7 2)
> (graph-add! g 8 9 72)
> (graph-add! g 9 10 7)
> (graph-add! g 9 6 31)
> (graph-add! g 9 8 18)
> (graph-add! g 10 6 8)
 > (define-values (dist1 prev1) (graph-shortest-path g 1))
> (shortest-path-to prev1 10)

(1 2 3)

> (hash-ref dist1 10)

18

 > (define-values (dist2 prev2) (graph-shortest-path g 1 (lambda (n) (= n 10))))
> (shortest-path-to prev2 10)

(1 2 3)

> (hash-ref dist2 10)

18