Re: Floyd Warshall

On 30 Ago, 10:30, Stefan Arentz <stefan.are...@xxxxxxxxx> wrote:
andrea <kerny...@xxxxxxxxx> writes:
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

I'm a lisp n00b, but maybe this is good advice.

What I usually do is chop up large functions into much smaller pieces
that can be tested individually in a unit test. I think there are a
few candidates in your code that could be taken out and thus also
tested independently. It is much easier to catch bugs that way and it
is also a good way to build up a library of utility functions and/or
macros.

S.

Yes you're right, but I don't have big functions, which ones you think
I could split?

Anyway after a couple of hours it works like a char :)

I changed this:
(defun add-to-min-dist (src dst infra k dist)
"aggiunge una riga alla tabella di hash"
(let
((key (list src dst 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 key min-dist) val)))))

It was adding for (c1 c2 k) and (c2 c1 k) at the same time, but that
was a mistake as long as I need the paths in the correct order...
And I fixed a couple of mistakes in the main algorithm, I was very
close.
Now I'll test on a very big file, let's see how slow it is!

.