Overview
All-Pairs Kürzeste Pfade mit dynamischer Programmierung; behandelt negative Kanten, nicht aber negative Zyklen.
Analogy
Jeden möglichen Zwischenort fragen: 'Komme ich von A über C nach B schneller als direkt?'
Step-by-step
- Initialisiere dist[i][j] = Kantengewicht oder ∞; dist[i][i]=0.
- Für jeden Zwischenknoten k: für jedes (i,j): dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]).
- Nach V Iterationen über k ist dist[i][j] der Kürzeste-Pfad für alle Paare.
Visual
V=3: iteriere k=0,1,2 – jede Runde prüft eine Zwischenstadt für alle Paare.
Common mistakes
- Schleifenreihenfolge: k ist äußerste Schleife, dann i, dann j – nicht i,j,k.
- Negativer Zyklus: dist[i][i] < 0 nach dem Algorithmus zeigt negativen Zyklus.
Practice questions
- Negative Zyklen mit Floyd-Warshall erkennen.
- Kürzesten Pfad zwischen jedem Paar in einem dichten Graphen finden.