Algorytm Floyda-Warshalla: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m Bot: Przenoszę 18 linków interwiki do Wikidata, znajdziesz je teraz w zasobie d:q1047576 |
|||
Linia 6:
: <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>
Algorytm jest [[Programowanie dynamiczne|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.
=== Wydajność algorytmu ===
| |||