Øv med flashcards — Korteste vei mellom alle par

Kapittel 11 · TDT4120

1 / 10

10 kort

Formel

Floyd-Warshall-rekurrensen

Formel

d_{ij}^{(k)} = min (d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)})

Tillater stadig flere mellomnoder: korteste vei fra $i$ til $j$ gjennom ${1.. k}$ er enten den uten $k$ , eller én som går via $k$ .

Tips: bruk piltastene for å bla og mellomrom/Enter for å snu kortet.