Einer der wichtigsten Anwendungsgebiete in der Graphentheorie ist die Untersuchung der optimalen Wege zwischen den Knoten. Dabei wird ein Weg als optimal bezeichnet, wenn er am kürzesten, am schnellsten oder am günstigsten ist. Je
nach Anwendung soll die Summe der Kanten die sich auf diesen Weg befinden optimal sein. Es gibt allgemein drei Verfahren für das Finden des optimalsten Weges: zwischen zwei beliebig gewählten Knoten, zwischen einem Startknoten und allen anderen Knoten und zwischen allen Paaren von Knoten. Diese Arbeit wird sich mit dem dritten Verfahren beschäftigen, auch bekannt unter dem Namen APSP-Problem. Bis einschließlich 2007 lag die optimalste Lösung in einer Laufzeit vonO(n^3/(log n)^c), 0 < c ≤ 2. 2014 gelang Ryan Williams [Wil13] ein besserer Ansatz.

Mit Tricks wie verbesserter Schaltungskomplexität, Zerlegung von Matrizen in kleinere Teilmatrizen und Methoden zur schnellen Polynom-Auswertung durch Matrix-multiplikation gelang es ihm ein deterministisches Verfahren abzuleiten mit einer Laufzeit von: n^3 ⋅ log M ⋅ poly(log log M)/2^((0.1 log n)^c).

Darüber hinaus entwickelte er auch ein randomisiertes Verfahren was dem deterministischen sehr ähnelt. Durch Manipulation der gegebenen Matrizen und randomisierten Techniken entwickelte Williams ein noch schnelleres Verfahren zur Lösung des APSP-Problems. Es liefert mit einer sehr hohen Wahrscheinlichkeit das richtige Ergebnis in einer Laufzeit von n^3/2^Ω(√ log n).

Die vorliegende Arbeit beschäftigt sich hauptsächlich mit der einfachen Beschreibung dieses komplexen randomisierten Verfahrens. Um das zu realisieren ergänzt diese Arbeit Williams Paper um eigene weiterführende Beispiele und Erklärungen. Dazu wird zunächst das APSP-Problem vorgestellt sowie nötige Erklärungen und Definitionen vorgenommen. Anschließend wird im Kapitel 2 das deterministische Verfahren und in Kapitel 3 das randomisierte Verfahren erläutert.

Zum Schluss wird ein Fazit gezogen, in dem die Auswirkungen der Arbeit von Williams auf andere Fragen und Probleme dargestellt werden. Zudem evaluiert der Autor seine Probleme und Schwierigkeiten mit dem Bearbeiteten des Papers.