4261638924

4

1    {Wejście: macierz D będąca macierzą wag luków}

2    {Wyjście: informacja o występowaniu w grafie ujemnego cyklu}

3    procedurę FWUC(L>);

4    begin

5    uc false; k := 1;

6    for i := 1 to n do    {wyznaczenie macierzy D⁰}

7    d[i,i] := 0;

8    end for;

9    while not uc and k    <    n    do

10    i := 1;

11    while not uc and i < n do    {wyznaczenie macierzy D^k)

12    if d[i, A;] ^ oo then

13    if d[i, fc] + d[k, i] < 0 then {znaleziono ujemny cykl}

14    uc := true;

15    else

16    for j := 1 to    n do

17    d[i,j] := min{d[i, j],d[i,k] + d[A:,j]};

18    end for:

19    end if:

20    end if;

21    i := *+ 1;

22    end while;

23    k:=k +1;

24    end while;

25    end.

Rys. 1. Algorytm wykrywania ujemnego cyklu za pomocą algorytmu Floyda-Warshalla

Mrowisko ma dwa wejścia znajdujące się odpowiednio w punktach 1 i 2, a także jedną spiżarnię znajdującą się w punkcie 7. Mrówki transportują pokarm z wejść do spiżarni, przy czym korytarzem łączącym dwa punkty mogą w ciągu jednego dnia przenieść ograniczoną ilość pokarmu (na rysunku zaznaczono ile maksymalnie pokarmu są w stanie przenieść mrówki). Stosując jeden z algorytmów przedstawionych na zajęciach, wyznacz maksymalną ilość pokarmu jaką są w stanie przenieść mrówki z wejść do spiżarni w ciągu jednego dnia. Nazwij zastosowany algorytm i przedstaw kolejne etapy jego działania.

Zadanie 17