Floyd-Warshall för alla par

Ibland behöver Ni hitta den kortaste vägen mellan alla par av noder, inte bara från en enda startnod. Det är problemet med alla par.

Floyd-Warshall fyller i en fullständig avståndstabell för alla par med tre enkla nästlade loopar och nästan ingen initiering.

Använd en matris där dist[i][j] är den bästa kända kostnaden från i till j. Initiera den med de direkta kanter som anges.

Varje nod når sig själv utan kostnad, så sätt diagonalen dist[i][i] till noll innan Ni börjar relaxera.

Tricket är att tillåta vägar att gå via en mellanliggande nod k och sedan fråga om vägen via k är billigare än den direkta vägen.

Den yttre loopen är k, den valda mellanpunkten. De inre looparna i och j provar varje par mot den mellanpunkten.

För varje par relaxerar Ni via k: om vägen från i till k och sedan till j är kortare uppdateras dist[i][j] till den sammanlagda kostnaden.

När k är färdigbehandlad kan alla par använda mellanliggande noder upp till k. Genom att placera k ytterst förblir den garantin korrekt.

Floyd-Warshall accepterar negativa kanter, men inte negativa cykler. En negativ cykel gör att något diagonalelement blir mindre än noll.

Tre loopar över n noder ger O(n^3) tidskomplexitet och O(n^2) minnesåtgång, vilket bara är praktiskt när n är högst några hundra.

Välj Floyd-Warshall när grafen är liten och tät och Ni verkligen behöver avståndet mellan varje par, inte bara avstånd från en enda startnod.

Initiera en matris, sätt diagonalen till noll och kör sedan looparna k, i, j för att relaxera via k. Kortaste vägar mellan alla par på O(n^3). 🧮