Re: Floyd Warshall

Another little thing, I also have a recursive version (the first I
did) which is working fine

(defun shortest-path (src dst k)
"algoritmo di calcolo principale, ritorna una cons della lista delle
tappe e la distanza totale.
Soluzione ricorsiva, piu' elegante ma purtroppo inutilizzabile con un
numero di citta anche piccolo"
(cond
((zerop k) (cons (list dst) (get-dist src dst)))
(T
(let*
((diretto (shortest-path src dst (1- k)))
(infra-list (remove src (remove dst cities))) ;; lista dei nodi che
possono essere intermediari
(min diretto)) ;; inizialmente il percorso diretto e' il minimo
(dolist
(inter infra-list)
;; (print (list src dst k inter infra-list))
(let
((before (shortest-path src inter (1- k))) (after (shortest-path
inter dst (1- k))))
(if
(> (cdr min) (+ (cdr before) (cdr after)))
(setq min (cons (append (car before) (car after)) (+ (cdr
before) (cdr after)))))))
min))))


BUT, for even a small number of cities (6) it take hours... That's
right because the numeber of function calls is factorial, but I think
there should be some ways to eliminate many calls...
Ideas?

.