warshall-floyd.lisp

(defun warshall-floyd (n edges)
  (let ((table (make-array (list n n) :initial-element 0)))
    (dolist (x edges)
      (destructuring-bind (from to weight) x
	  (setf (aref table from to) weight)))
    (dotimes (k n)
      (dotimes (i n)
	(dotimes (j n)
	  (when (> (aref table i j)
		   (+ (aref table i k) (aref table k j)))
	    (setf (aref table i j)
		  (+ (aref table i k) (aref table k j)))))))))

(defun warshall-floyd-optimized (n edges)
  (declare (optimize (speed 3) (debug 0) (safety 0))
	   (fixnum n))
  (let ((table (make-array (list n n) :element-type 'fixnum
			   :initial-element 0)))
    (dolist (x edges)
      (destructuring-bind (from to weight) x
	(setf (aref table from to) weight)))
    (dotimes (k n)
      (dotimes (i n)
	(dotimes (j n)
	  (let ((cand (the fixnum (+ (the fixnum (aref table i k))
				     (the fixnum (aref table k j))))))
	    (when (> (the fixnum (aref table i j)) cand)
	      (setf (aref table i j)
		    cand))))))))