algorytm.org

Algorytm Floyda



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Floyda
Ocena użytkowników:***** / 15
SłabyŚwietny 
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ść:
Image Image
Oto przebieg obliczeń:
d(i,j)=A(i,j)
d123456
1024nnn
2n0nn4n
3nn0-23n
41nn0n2
5nnnn0n
6n2nn10
k=1
d123456
1024nnn
2n0nn4n
3nn0-23n
41350n2
5nnnn0n
6n2nn10
k=2
d123456
1024n6n
2n0nn4n
3nn0-23n
4135072
5nnnn0n
6n2nn10

k=3
d123456
102426n
2n0nn4n
3nn0-23n
4135072
5nnnn0n
6n2nn10

k=4
d123456
1024264
2n0nn4n
3-110-230
4135072
5nnnn0n
6n2nn10

k=5
d123456
1024264
2n0nn4n
3-110-230
4135072
5nnnn0n
6n2nn10

k=6
d123456
1024254
2n0nn4n
3-110-210
4135032
5nnnn0n
6n2nn10

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 3
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 0
Tomasz LubińskiJava
.java
.java
***** / 5
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 17 sierpnia 2012 15:43
Komentarze
photo
-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ć
photo
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ć
photo
-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