Wikipedia

Algorytm Floyda-Warshalla: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
literówka
Linia 4:
== Opis algorytmu ==
 
[[Algorytm]] Floyda-Warshalla korzysta z tego, że jeśli najkrótsza ścieżka pomiędzy wierzchołkami ''v<sub>1</sub>'' i ''v<sub>2</sub>'' prowadzi przez wierzchołek ''u'', to jest ona połączeniem najkrótszych ścieżek pomiędzy wierchołkamiwierzchołkami ''v<sub>1</sub>'' i ''u'' oraz ''u'' i ''v<sub>2</sub>''. 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 (''v<sub>1</sub>'',''v<sub>2</sub>'') ich odległość wynosi:
:<math>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}</math>
 
Źródło: „https://pl.wikipedia.org/wiki/Algorytm_Floyda-Warshalla”