Kürzeste-Wege-Problem

Kürzeste-Wege-Probleme sind durch folgende Probleme beschrieben:

• Gegeben ist ein gerichteter, gewichteter Graph
• Gesucht ist der kürzeste Weg von einem bzw. allen, zu einem bzw. allen Knoten

Arten

Kürzester Weg von…	zu…	Beziehung	Englisch
einem Knoten	einem anderen Knoten	1:1	single-pair shortest path
einem Knoten	allen anderen Knoten	1:n	single-source shortest paths
allen Knoten	einem bestimmten Knoten	n:1	single-destination shortest paths
allen Knoten	allen anderen Knoten	n:n	all-pairs shortest paths

Algorithmen

Für 1:n

• Ungewichtete Graphen:
  • Am besten durch Breitensuche mit Laufzeit
• Gewichtete Graphen:
  • Nicht negative Kantengewichte: Dijkstra-Algorithmus mit Laufzeit
  • Beliebige Kantengewichte: Bellmann-Ford-Algorithmus mit Laufzeit

Für n:n - Das APSP-Problem

• Lösbar mit 1:n-Algorithmen, die man für jeden Knoten anwendet
  • Für die Laufzeit bedeutet das einen Zuwachs von Faktor
  • Dijkstra-Algorithmus hat dann die Laufzeit
  • Bellmann-Ford-Algorithmus mit Laufzeit )
    • Bei dichten Graphen wird die Laufzeit sogar
• Besser: APSP

Formulierung als Lineares Programm

Kürzeste-Wege-Probleme können auch als lineares Programm formuliert werden. Siehe hierzu Kürzeste-Wege-Problem als Lineares Programm