Korteste vei fra alle til alle

En slags utvidelse av Korteste vei fra en til alle. Vi har fortsatt en vektet rettet graf, $G=(V,E)$, som er definert sammen med en vektmatrise $W$.

---

En naiv løsning ville vært å kjøre Dijkstras algoritme på hver node for å finne korteste vei fra alle til alle. Dersom vi ikke har negative sykler kan vi kjøre Bellman-Ford på alle, men dette vil gi en kjøretid på $O(V^{2}E)$, som betyr at en Dens graf - Dense Graph vil ha en kjøretid på $O(V^4)$.

---

Det er derimot mange overlappende delinstaner, og derfor gunstig å bruke Dynamisk programmering.

---

Korteste vei fra alle til alle Algoritme - Algorithms bruker hovedsakelig Nabomatriser istedenfor Nabolister.

Algoritmer

Johnsons algoritme Transitive Closure Floyd-Warshalls algoritme

---

SLOW-APSP FASTER-APSP

Hjelpefunksjoner

PRINT-ALL-PAIRS-SHORTEST-PATH EXTENDED-SHORTEST-PATHS

Notasjon

Vi skriver ofte matrise som en stor bokstav, etterfulgt av subscript letters.

$$L^{(r)}=(l_{ij}^{(r)})$$

Eller

$$D^{(r)}=(d_{ij}^{(r)})$$