DeathKing
commented
3 years ago Looks like Juha Heinanen 1988 was the original author. Maybe you never ran dijkstra2.
You're quite right, as the mention in experiment3/reference/README.md, codes under that reference folder are not written by me, even through, they throw some light on the implementation of the specific algorithm. For that purpose, I just collected and put them there.
Through, this repository was created when I was also a newbie to Lisp/Scheme. Some code may inherit the imperative natural of the algorithm, with side-effect which is not the paradigm of functional programming.
If you want to learn Lisp/Scheme, this repo is not a good start, I strongly recommend you the SICP course instead. If you want to learn data structure and algorithms, especially the functional version, I recommend you following books:
- Richard Bird, Pearls of Functional Algorithm Design
- Chris Okasaki, Purely Functional Data Structures
Using your code as listed I get:
1 ]=> (dijkstra2 c)
;The procedure #[compiled-procedure 16 ("vector" #xa) #x1a #xbd14fa] has been called with 4 arguments; it requires exactly 3 arguments. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
I fixed parenthesis so that dijkstra2 is now:
(define (dijkstra2 C)
; computes a pair of vectors which contain ; (1) the costs of the shortest paths from vertex 0 ; to every vertex in the cost matrix C and ; (2) the immediate predecessor vertexes of every ; vertex in the shortest path
(define n (matrix-col-length C))
(define D (matrix-row-copy C 0)) ; shortest distance from vertex 0 to each vertex
(define P (make-vector n 0)) ; P[v] contains the vertex immediately before ; vertex v in the shortest path
(define (min-vertex D V) ; chooses a vertex w in V such that D[w] is minimum (let loop ((w (car V)) (V (cdr V))) (if (null? V) w (if (< (vector-ref D (car V)) (vector-ref D w)) (loop (car V) (cdr V)) (loop w (cdr V))))))
; dijkstra (let loop ((V (enum 1 (- n 1)))) ; V contains the set of vertexes whose shortest ; distance from the vertex 0 is still unknown (if (null? V) (cons D P) (let* ((w (min-vertex D V)) (V-w (remv V w))) (for-each (lambda (v) (if (< (+ (vector-ref D w) (matrix-ref C w v)) (vector-ref D v)) (begin (vector-set! D v (+ (vector-ref D w) (matrix-ref C w v))) ;;; added ) (vector-set! P v w)))) ;;; removed ) V-w) (loop V-w)))))
Now I get:
1 ]=> (dijkstra2 c)
;Value: (#(0 10 50 30 60) . #(0 0 3 0 2))
See comments in code above for the tiny edit (moved a close paren).
Looks like Juha Heinanen 1988 was the original author. Maybe you never ran dijkstra2.
Thank you so much for posting this code. Incredibly helpful to a lisp newbie like me.