Wpisany przez Tomasz Lubiński,
09 sierpnia 2005 20:37
Algorytm ten służy do wyznaczania najmniejszej odległości pomiędzy wszystkimi parami wierzchołków w skierowanym grafie bez cykli o ujemnej długości.
Warunek nieujemności cyklu jest spowodowany faktem, że w grafie o ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami jest nieokreślona, ponieważ zależy od liczby przejść w cyklu.
Algorytmu tego można również użyć do obliczenia domknięcia przechodniego relacji binarnej przedstawionej w postaci grafu skierowanego G. Wówczas domknięcie przechodnie definiuje się jako: En={(x,y): istnieje w G droga o niezerowej długości od x do y} (przy tej definicji każda krawędź ma wagę 1).
Dla podanego grafu macierz A dla każdej pary wierzchołków u i v zawiera wagę krawędzi (u,v), przy czym jeśli krawędź (u,v) nie istnieje, to przyjmujemy, że jej waga wynosi nieskończoność.
Algorytm Floyda opiera się na następującym spostrzeżeniu. Niech dij(k) oznacza długość najkrótszej spośród dróg vi do vj o wierzchołkach pośrednich w zbiorze {v1,...,vk} Stąd:
dij(0)=Aij (połączenie przez jedną krawędź)
dij(k+1)=min{dij(k), di k+1(k)+dk+1 j(k)}
Pseudokod wygląda następująco:(n- liczba wierzchołków)
begin;
for i:=1 to n do
for j:=1 to n do d(i,j)=A(i,j);
for i:=1 to n do d(i,i)=0;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
d(i,j)=min( d(i,j), d(i,k)+d(k,j) );
end;
Dla przykładu oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
symbol "n" lub "*" oznacza nieskończoność:
Oto przebieg obliczeń:
Warunek nieujemności cyklu jest spowodowany faktem, że w grafie o ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami jest nieokreślona, ponieważ zależy od liczby przejść w cyklu.
Algorytmu tego można również użyć do obliczenia domknięcia przechodniego relacji binarnej przedstawionej w postaci grafu skierowanego G. Wówczas domknięcie przechodnie definiuje się jako: En={(x,y): istnieje w G droga o niezerowej długości od x do y} (przy tej definicji każda krawędź ma wagę 1).
Dla podanego grafu macierz A dla każdej pary wierzchołków u i v zawiera wagę krawędzi (u,v), przy czym jeśli krawędź (u,v) nie istnieje, to przyjmujemy, że jej waga wynosi nieskończoność.
Algorytm Floyda opiera się na następującym spostrzeżeniu. Niech dij(k) oznacza długość najkrótszej spośród dróg vi do vj o wierzchołkach pośrednich w zbiorze {v1,...,vk} Stąd:
dij(0)=Aij (połączenie przez jedną krawędź)
dij(k+1)=min{dij(k), di k+1(k)+dk+1 j(k)}
Pseudokod wygląda następująco:(n- liczba wierzchołków)
begin;
for i:=1 to n do
for j:=1 to n do d(i,j)=A(i,j);
for i:=1 to n do d(i,i)=0;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
d(i,j)=min( d(i,j), d(i,k)+d(k,j) );
end;
Dla przykładu oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
symbol "n" lub "*" oznacza nieskończoność:
d(i,j)=A(i,j)
| k=1
|
k=2
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
k=3
| k=4
| k=5
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
k=6
|
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 3 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 0 | |
Tomasz Lubiński | Java | .java | .java | ***** / 5 |
Poprawiony: 17 sierpnia 2012 15:43
Komentarze
-1
#
PanKazimierz
2009-10-14 10:52
Przydal by sie jeszcze opis w jaki sposob odtorzyc najkrotsza scierzke z macierzy poprzednikow. Pozatym opis o wiele lepszy niz na wikipedi :-).
Odpowiedz | Odpowiedz z cytatem | Cytować
0
#
Tomek
2009-10-14 20:56
Domyślam się, że brakowało linku do wyznaczania drogi (algorytm.org/index.php?option=com_content&task=view&id=91&Itemid=28)
Odpowiedz | Odpowiedz z cytatem | Cytować
-1
#
Gril
2010-12-30 09:27
Kod do C++ jest zbędny if lepiej poprostu zrobić to bez ifa i odrazu wybierać min za nieskończoność dać bardzo dużą liczbe
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz