Floyd Warshall

In a few words I have to find the minimum distance between many
cities, where
(get-dist c1 c2)
tells me the distance (100 if there are no direct path).

This is the algorithm

(defun floyd-warshall ()
"crea una tabella n*n con le distanze piu brevi fra le citta"
;; primo ciclo imposta i collegamenti diretti fra le citta (k == 0)
;; citta con se stesse
(setq min-dist nil)
(dolist (c1 cities)
(let*
((pos (position c1 cities)) ;; in questo modo minimizzo le chiamate a
get-dist
(sublist (drop pos cities)))
(dolist (c2 sublist)
(add-to-min-dist c1 c2 (list c2) 0 (get-dist c1 c2))))) ;; add-to-min-
dist aggiunge anche al simmetrico
;; ora vado iterativamente a calcolare tutte le distanze minime
(do
((k 1 (incf k)))
((equal k (length cities)))
(dolist (c1 cities)
;; (let*
;; ((pos (position c1 cities :test 'equal)) ;; in questo modo
minimizzo le chiamate a get-dist
;; (sublist (drop (1+ pos) cities)))
(dolist (c2 cities)
(let*
((direct (get-min-path c1 c2 (1- k)))
(before (get-min-path c1 (nth (1- k) cities) (1- k)))
(after (get-min-path (nth (1- k) cities) c2 (1- k)))
(total (cons (append (car after) (car before)) (+ (cdr before)
(cdr after)))))
(if
(<= (cdr direct) (cdr total)) ;; preferisco i percorsi diretti
;; il percorso diretto per k-1 nodi e' il piu breve
(add-to-min-dist c1 c2 (car direct) k (cdr direct))
;; percorso con una tappa
;;TODO aggiustare questo stupido problema di indici
(add-to-min-dist c1 c2 (car total) k (cdr total))))))))

And it almost works, but sometimes it doesn't find the shortest route,
and I don't really understand why...

This is the implementation of the min-dist table (hash-table)

(defun add-to-min-dist (src dst infra k dist)
"aggiunge una riga alla tabella"
(let
((key1 (list src dst k)) (key2 (list dst src k))
(val (cons infra dist)))
(cond
((null min-dist)
(setq min-dist (make-hash-table :test 'equal))
(add-to-min-dist src dst infra k dist))
(t (setf (gethash key1 min-dist) val)
(if (not (equal src dst))
(setf (gethash key2 min-dist) val))))))

(defun get-min-path (src dst k)
"prende dalla tabella di hash"
(gethash (list src dst k) min-dist))

Any suggestion (even for style) is welcome...

PS. I just trasnlated this algorithm
floyd-warshall(W):
n = rows[W]
D(0) = W
for k in (1,n):
for i in (1,n):
for j in (1,n):
dij(k) = min(dij(k-1),***(k-1)+dkj(k-1))

and I don't see where is the mistake..

.

Quantcast