鄰接矩陣/ Floyd/Warshall in lisp

顯然，我的老師認爲即使我們沒有時間學習東西（也沒有足夠的例子），我們應該繼續前進，所以我現在需要知道如何製作Floyd-Warshall和Warshall的算法在clisp中。鄰接矩陣/ Floyd/Warshall in lisp

當我同序言一樣，我的問題是，產生從圖中的鄰接矩陣，在這種情況下，這將是列表的列表，如：

((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 
)

任何幫助是極大的讚賞。

另外，還有一種題外話：如果我能解決我自己的問題，我是否應該回答自己是否有回答問題？

來源

2011-05-24 Kirby

有一個[SelfLearner徽章]（http：// stackoverflow .com /徽章/ 14 /自學者），如果你用3或更多的分數回答你自己的問題。我會以此作爲暗示，回答自己是否可以接受解決方案。 – 2011-05-24 22:49:38

作爲更多慣用代碼的開始，使用['let']（http://www.lispworks.com/documentation/HyperSpec/Body/s_let_l.htm）代替'l'，'mat'的'setf'和'matrix'。 – 2011-05-24 22:54:51

CLISP是一個實現，該語言被稱爲Common Lisp或簡稱CL。您還需要聲明變量（例如使用LET）。設置任意未定義的變量不是一個好主意。也不要在一行上用單個括號格式化代碼。 – 2011-05-24 23:21:30

我使用類型聲明將Wikipedia僞代碼轉換爲Common Lisp。返回類型聲明是非標準的，我使用SBCL。我想這不會運行，但它可能會給你一個想法如何Lisp代碼應該看起來像。

(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)

注1：如果你有一個三維體積圖像，你應該有你的指數是這樣（AREF體積ķĴI），其中k指數ž，J y和我x方向。在SBCL中這種方式，並且可能所有其他實現中的片在存儲器中是連續的。

注2： macrolet可以節省相當多的輸入。還可以看看這個漂亮的庫中帶數組的實現：git：//github.com/nikodemus/raylisp.git/objects/box.lisp

來源

2011-07-01 14:42:09 whoplisp

鄰接矩陣/ Floyd/Warshall in lisp

回答

相關問題