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.
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.