Johnsons algoritme kjører en kombinasjon av Bellman-Ford og Dijkstra. Det som er spesielt med denne algoritmen er hvordan den justerer kantvekter, selv når de er negative.
Algoritmen returnerer enten en matrise for alle korteste vei vektene for alle nodeparene eller rapporterer at det finnes negative sykler i grafen.
Hvis vi har få kanter og kun positive kanter lønner det seg å bruke Dijkstras algoritme fra alle nodene. Har vi derimot negative kanter og relativt få kanter er Johnsons algoritme løsningen.
Johnsons øker kantvektene, men vi kan ikke øke alle kantvektene med det største negative kantens vekt, da blir de nodene med mange kanter urettmessige "dyre". Vi er ikke garantert å bevare rangeringen av stiene om vi øker kantvektene med en konstant.
Johnsons implementerer løser dette ved å implementere en "teleskopsum". En sum som kollapser som et teleskop. Annenhvert ledd er minus det forrige. Vi ønsker at langs en hver sti skal ha en teleskopsum.
Algoritmen tilordner hver node en verdi og så endrer vi kantvekten med differansen av de to verdiene. Kanten fra
- Trinn 5-6 er der teleskopsummen implementeres
- Trinn 7-11 er der matrisen med korteste vei fra alle til alle genereres.
Om det er relativt få kanter som er negative så er Johnsons et godt valg.
Med Fibonacci-haug:
Med binære min-heap: $O(VElgV)$
| Best case | Average case | Worst case | Minne |
|---|---|---|---|
| TODO | TODO | TODO |