邻接矩阵/ Floyd / Warshall以Lisp表示
||
显然，我的老师认为，即使我们没有时间学习东西（也没有足够的例子），我们也应该继续前进，所以我现在需要知道如何使Floyd-Warshall's和Warshall's算法变得一帆风顺。
就像我在序言中所做的那样，我的问题是从图生成邻接矩阵，在这种情况下，它将是列表的列表，例如：
((A B) (A C) (A D) (B C) (C D))
((0 1 1 1) (1 0 1 9) (1 1 0 1) (1 9 1 0))
(defun floyd(graph)
(setf l (length graph))
(setf mat (matrix l graph))
)
(defun matrix(l graph)
(setf matrix (make-array (list l l)))
(dotimes (i l)
(dotimes (j l)
(if (= i j)
(setf (aref matrix i j) 0)
(setf (aref matrix i j) ???)
)
)
)
matrix
)
没有找到相关结果
已邀请:
1 个回复
亨尖玛次酥
(defparameter *n* 5) (defparameter *path* (make-array (list *n* *n*) :element-type \'(unsigned-byte 64))) (defun floyd-warshall (path) (declare (type (simple-array (unsigned-byte 64) 2) path) (values (simple-array (unsigned-byte 64) 2) &optional)) (destructuring-bind (y x) (array-dimensions path) (unless (= y x) (break \"I expect a square matrix, not ~ax~a.\" x y)) (macrolet ((p (j i) `(aref path ,j ,i))) (dotimes (k x) (dotimes (i x) (dotimes (j x) (setf (p j i) (min (p j i) (+ (p k i) (p j k))))))))) path)