Hvorfor er det nok å relaxe alle kanter \(V\mkern-2mu-1\) ganger hver for å oppnå korteste vei i Bellman-Ford?

Basert på Piazza-spørsmål fra 2015

Godt spørsmål!

Det handler om en form for konvergens: Hvis du oppdaterer (relaxer) alle kantene i én av de korteste veiene i riktig rekkefølge, så vil du ende opp med rett svar for endenoden, fordi du først får et minimalt svar for den andre noden, så den tredje, etc. Og å oppdatere andre kanter (evt. andre kanter på den samme stien, men utenfor den rekkefølgen) vil ikke gjøre svaret dårligere, då dem kan du ignorere.

Resultatet av dette er at hvis en av de korteste stiene består av \(k\) kanter, så vil du ha funnet den etter å ha oppdatert alle kantene \(k\) ganger – for da vil du garantert (innimellom alt det andre) ha oppdatert disse \(k\) kantene i riktig rekkefølge. Den første (… og alle de andre) i første iterasjon, den andre (… og alle de andre) i andre iterasjon, etc.

Så hvis vi vet at ingen stier består av mer enn f.eks. 100 000 kanter, vil det være nok med 100 000 iterasjoner. Mer generelt vet vi jo at de korteste stiene ikke har løkker, så de kan heller ikke ha flere enn \(E\) kanter, så \(E\) iterasjoner vil også være nok. Men: Om de ikke har sykler, kan jo hver node også bare delta i en sti maks én gang. Så en kortest sti vil ha maks \(V\) noder, og dermed maks \(V\mkern-2mu-1\) kanter, som gir svaret.