@FredlFesel: Was ist all-pair-shortest-path? Die beiden begriffe single und all pair waren mir noch nicht begegnet o.O
Single-Pair Shortest Path= Finde kürzesten Weg für ein Paar (Anfangspunkt, Endpunkt)
All-Pair Shortest Path = Finde die kürzesten Weg zwischen allen Punkte im Graph.
Man kann sich das Wissen, das man bei der Suche nach einem kürzesten Weg für das Finden anderer kürzester Wege zu Nutze machen.