a

j

W wierszu k (oprócz kk) zanotowane są łuki wychodzące OD wierzch. k

W kolumnie k (oprócz kk) zanotowane są łuki wchodzące DO wierzch. k

k

k

Rys. 5-3. Przykład oprogramowania algorytmu Warshalla-Floyda
dla rzadkich tablic IM i W.

Fragment procedury redukcji wierzchołków n..0 bez ich eliminacji wg algorytmu Warshalla - Floyda

1. for k:=n downto 0 do {k odpowiada numerowi wierzchołka redukcji}

2. for i:=n downto 0 do {i odpowiada łukowi skierowanemy DO wierz. k}

3. begin

4. if Im[i,k]='' then continue; { nie ma łuku skierowanego od i do k }

5. for j:=n downto 0 do {j odpowiada łukowi skierowanemy OD w. k}

6. begin

7. if (Im[k,j]='') OR (i=j) then continue; {łuki (ik),(kj) są zerowe lub symetr.}

8. Inc(Lij); { Lij - licznik nie zerowych par (ik),(kj) }

9. if ((Im[i,j]='') { tzn. nie ma „starego” łuku (i,j) }

10. OR (W[i,j] > W[i,k]+W[k,j])) { tzn. nowy łuk jest „tańszy” od starego }

11. then begin Inc(Lzn); {Lzn - licznik zapisów do tablic W, IM}

12. W[i,j]:= W[i,k]+W[k,j]; Im[i,j]:=Im[i,k]+Im[k,j];

13. {...tu drukujemy nowy łuk...}

14. end; {pętla zapisu oraz drukowania łuku}

15. end; {pętla po j}

16. end; {pętla po i}

IM: array [0..n, 0..n] of string [30];

W: array [0..n, 0..n] of double;

i,j<n; i≠j

n

n

n

n

2

0

0

IM (imie)

W (waga)

30

a=2

i

Tablicowa interpretacja digrafu

j

i

i

j

---