En Algoritme - Algorithms for å finne korteste vei fra alle til alle, der vi kan ha negative kantvekter. I motsetning til Johnsons algoritme må vi ikke gjøre kantene positive. Resultatet er en Nabomatriser med korteste avstand mellom nodene.
Vi bruker Dynamisk programmering.
Pseudokode og kjøretid
Kjøretid:
Virkemåte
Fungerer på ganske lik måte som Transitive Closure. Vi sjekker veier som går gjennom node , men bruker derimot denne formelen istedenfor