abgeschlossen 

Das ”Single-Source Shortest-Path“-Problem (SSSP) ist ein seit vielen Jahren mit großem Interesse studiertes Problem der Algorithmik, für das viele sehr gute sequentielle Algorithmen bekannt sind. Die bislang vorgeschlagenen Algorithmen für parallele Rechner haben allerdings noch mit mehr oder weniger großen Einschränkungen zu kämpfen. So ist bislang kein Algorithmus bekannt, der das SSSP auf Straßengraphen effizient löst. Straßengraphen besitzen besondere Eigenschaften, die für die existierenden parallelen SSSPAlgorithmen ein Problem darstellen. Insbesondere der geringe Ausgangsgrad der Knoten (im Schnitt 2,25) und die sehr unterschiedlichen Kantengewichte (zwischen wenigen Metern und mehreren Kilometern) sind eine große Herausforderung. Ich stelle in dieser Arbeit einen Algorithmus und dessen Implementierung vor, der einen Beitrag zur effizienteren parallelen Berechnung des SSSP auf Straßengraphen leisten und dabei auch auf anderen Graphen keine schlechteren Ergebnisse erzielen soll.