Prof. Dr. Franz J. Brandenburg

(Universität Passau)

Januar 2003

Vortrag im Rahmen des Informatik-Kolloquiums:

Kürzeste Wegeprobleme treten in vielen Anwendungen auf, z.B. bei der Routenplanung oder dem Auffinden von schnellsten oder billigsten Verbindungen. Für diese klassische Aufgabenstellung gibt es effiziente Lösungsalgorithmen z.B. von Dijkstra oder Bellman­Ford.

Verallgemeinerte Graphen haben zwei Parameter auf den Kanten. Diese bedeuten verschiedene Kostenkriterien, z.B. Zeit und Geld oder Kosten und Zuwächse. Letzteres ist als "transshipment problem" seit Kantorovich (1939) bekannt. Bei prozentualen Zuwächsen wird der Fluß oder die Geldmenge durch die Nutzung einer Kante um einen Faktor verkleinert oder vergrößert. Dies ergibt sich durch die Verdunstung von Flüssigkeiten oder Gebühren auf Geldgeschäften. Die Kosten werden je Einheit erhoben. Gesucht ist der billigste Weg für eine Starteinheit.

Für dieses billigste Wegeproblem wird ein neuer Algorithmus vorgestellt. Es ist eine Variante des bekannten Bellman­Ford Verfahrens mit eine Laufzeit von nur O(n m log n). Zyklen spielen dabei eine besondere Rolle. Dem gegenüber stehen Problemstellungen bei denen die Berechnung des billigsten Weges NP­schwer ist, z.B. längste Wege, exakte Wege und verallgemeinerte Wege zwischen zwei Knoten. Neben den Problemstellungen und Lösungsalgorithmen werden auch die in diesem Umfeld offenen Probleme angesprochen.