Version: 4.1.5.3
Dijkstra’s Algorithm
(require (planet jaymccarthy/dijkstra:1:0)) |
This package provides an implementation of Dijkstra’s Algorithm that uses a Fibonacci heap for the queue.
| ||||||||||||||||||||||||||||||||||||||
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.
1 Example
(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) | ||
| ||
> (shortest-path-to prev1 10) | ||
(1 2 3) | ||
> (hash-ref dist1 10) | ||
18 | ||
| ||
> (shortest-path-to prev2 10) | ||
(1 2 3) | ||
> (hash-ref dist2 10) | ||
18 |