deathking / hit-datastructure-on-scheme Goto Github PK

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.

如果您认为我的解法有错误或者过于笨拙，我 欢饮 您提交Pull Request

应该是 欢迎 吧

第19行和第22行的两个函数stack-empty?和stack-size，应该用(stack s)而不是(cdr s)。

首先，感谢楼主提供的环境资源分享。但是现在我的64位环境采用make编译linux-0.11出现了as86:Command not found的问题，所以在此处想请教一下楼主该如何解决，谢谢啦！