Algorytm Floyda-Warshalla
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Algorytm Floyda-Warshalla służy do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonym.
[edytuj] Opis algorytmu
Algorytm Floyda-Warshalla korzysta z tego, że jeśli najkrótsza ścieżka pomiędzy wierzchołkami v1 i v2 prowadzi przez wierzchołek u, to jest ona połączeniem najkrótszych ścieżek pomiędzy wierzchołkami v1 i u oraz u i v2. Na początku działania algorytmu inicjowana jest tablica długości najkrótszych ścieżek, tak że dla każdej pary wierzchołków (v1,v2) ich odległość wynosi:
![d[v_1,\,v_2]=\begin{cases} 0, & \mbox{gdy}\ v_1=v_2\\ w(v_1,\,v_2), & \mbox{gdy}\ (v_1,\,v_2)\in E \\ +\infty, & \mbox{gdy}\ (v_1,\,v_2)\not\in E\end{cases}](http://upload.wikimedia.org/math/1/6/5/165ad3070e3bf2c0d2b3edd034b468e0.png)
Algorytm jest dynamiczny i w kolejnych krokach włącza do swoich obliczeń ścieżki przechodzące przez kolejne wierzchołki. Tak więc w k-tym kroku algorytm zajmie się sprawdzaniem dla każdej pary wierzchołków, czy nie da się skrócić (lub utworzyć) ścieżki pomiędzy nimi przechodzącej przez wierzchołek numer k (kolejność wierzchołków jest obojętna, ważne tylko, żeby nie zmieniała się w trakcie działania programu). Po wykonaniu |V| takich kroków długości najkrótszych ścieżek są już wyliczone.
[edytuj] Wydajność algorytmu
- Złożoność obliczeniowa:
- Złożoność pamięciowa:
[edytuj] Zapis w pseudokodzie
Dla grafu G i funkcji wagowej w otrzymamy tablicę d[v1][v2] odległości pomiędzy wierzchołkami v1 i v2.
Floyd-Warshall(G,w)
dla każdego wierzchołka v1 w V[G] wykonaj
dla każdego wierzchołka v2 w V[G] wykonaj
d[v1][v2] = nieskończone
poprzednik[v1][v2] = niezdefiniowane
d[v1][v1] = 0
dla każdej krawędzi (v1,v2) w E[G]
d[v1][v2] = w(v1,v2)
poprzednik[v1][v2] = v1
dla każdego wierzchołka u w V[G] wykonaj
dla każdego wierzchołka v1 w V[G] wykonaj
dla każdego wierzchołka v2 w V[G] wykonaj
jeżeli d[v1][v2] > d[v1][u] + d[u][v2] to
d[v1][v2] = d[v1][u] + d[u][v2]
poprzednik[v1][v2] = poprzednik[u][v2]
Zobacz też: problem najkrótszej ścieżki, algorytm Johnsona
| Fragmenty gekona sprzed 100 mln lat w bursztynie |
|
Fragmenty gekona sprzed 100 mln lat zamknięte w bursztynie odkryli naukowcy ze Stanów Zjednoczonych i Wielkiej Brytanii. O swoim odkryciu informują na łamach naukowego pisma "Zootaxa".
|
| Największy eksperyment w historii nauki |
|
Za kilka dni, 10 września, rusza największy eksperyment w historii nauki. W Alpach, pod granicą szwajcarsko-francuską schowano tunel o obwodzie 27 kilometrów. Nazwano go Wielkim Zderzaczem Hadronów i naukowcy wierzą, że eksperymenty tam przeprowadzone dadzą odpowiedź na najbardziej fundamentalne pytania o wszechświat. Obszerny opis eksperymentu znajdziemy w "Magazynie "Dziennika".
|
| Kurhany na Wyżynie Sandomierskiej |
|
Wygląda jak niepozorny pagórek, czasem oznaczony kilkoma przewróconymi głazami. Kiedy rolnicy obrabiają swoje pola, często zahaczają o niego, a jeśli głazy da się odsunąć - zrównują z ziemią. Czasem orka odsłania kamienne bloki, rzadziej odkrywa szkielety pochowanych tu ludzi. Zdarza się jednak, że kurhan, czyli nasyp nad pradawnym grobowcem, opiera się działaniu czasu. Wówczas archeolodzy mogą zająć się jego ochroną lub zbadać.
|
| Bezpieczne sposoby leczenia cukrzycy |
|
Poziom leczenia cukrzycy w Polsce jest raczej średni, ale wielu powikłaniom można zapobiec właściwie przyjmując leki - powiedział prof. Edward Franek ze Szpitala klinicznego MSWiA na konferencji prasowej, zorganizowanej przez Urząd Rejestracji Produktów Leczniczych, Wyrobów Medycznych i Produktów Biobójczych.
|
| Czysta woda bez narkotyków |
|
Nowoczesne metody oczyszczania wody pitnej stanowią doskonała barierę eliminującą zawarte w niej pierwotnie psychoaktywne substancje chemiczne np. kokainę, amfetaminę, kofeinę czy nikotynę (oraz ich pochodne), donosi "Environmental Science & Technology".
|