Das Kürzeste-Wege-Problem ist ein fundamentales Problem der Graphentheorie. Für den Fall der Berechnung auf Graphen mit ausschließlich positiven Kantengewichten haben sich schon länger Algorithmen etabliert, welche das Problem in nahe-linearer Laufzeit berechnen. Ein Beispiel dafür ist der Algorithmus nach Dijkstra. Werden nun Graphen mit beliebigen, sprich auch negativen Kantengewichten betrachtet, so produzieren diese Algorithmen, insbesondere der Dijkstra-Algorithmus, meist falsche Ergebnisse. Algorithmen, die in den letzten Jahren für beliebige Graphen entwickelt wurden, zeigen, dass immer näher an die nahezu lineare Komplexität herangekommen ist. So schaffte erstmals der Algorithmus von Bernstein et al. im Jahre 2022, eine Komplexität von O(m · log^8(n) · log(W)) aufzuweisen. In dieser Arbeit werden drei eigene Ansätze entwickelt, welche auf beliebigen gerichteten Graphen einen Kürzeste-Wege-Baum berechnen. Diese sollen auf Laufzeit und Korrektheit geprüft und anschließend in einer Simulation verglichen werden. Die Simulation erfolgt auf zwei Graphenmodellen, wodurch möglichst zufällige Graphen generiert werden. Dazu werden auch unterschiedliche Knoten- und Kantenanzahlen betrachtet.
Aus den entwickelten Ansätzen stellt sich Ansatz 3 als schnellster Algorithmus heraus. Dabei übertrifft er jedoch nicht den Bellman-Ford-Algorithmus. Die Ansätze 1 und 2 werden aufgrund ihrer Vorberechnungen rechenzeittechnisch abgehängt. Während Ansatz 1 noch akzeptable Zeiten liefert, benötigt Ansatz 2 dank weiterer Berechnungen ein Vielfaches länger.