Kürzester Pfad

Grundidee und Definition

Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten s,t ∈ V eines Graphen, dessen Länge bezüglich einer Kantengewichtsfunktion c: E → ℝ minimal ist. Die Länge eines Pfades ergibt sich aus der Summe der Gewichte seiner Kanten. Die Knoten s und t werden meist als Start- und Zielknoten bezeichnet.

Sind alle Kantengewichte gleich 1, also c(e) = 1 für alle e ∈ E, besteht ein kürzester Pfad aus der geringstmöglichen Anzahl von Kanten zwischen s und t. Die Berechnung eines solchen Weges ist ein Optimierungsproblem und wird häufig als Shortest Path Problem oder als Single-Source Shortest Path (SSSP) bezeichnet.

Wichtig ist die Unterscheidung zwischen einem Pfad und einem Kantenzug: In einem Kantenzug dürfen Knoten und Kanten mehrfach vorkommen, während ein Pfad keinen Knoten doppelt verwendet. Unter den üblichen Zusatzbedingungen, insbesondere bei nichtnegativen oder konservativen Gewichtsfunktionen, ist jeder kürzeste Pfad zugleich ein kürzester Kantenzug.

Gewichte und Komplexität

Die Komplexität hängt vor allem von der Gewichtsfunktion und davon ab, ob Pfade oder Kantenzüge gesucht werden. Eine Gewichtsfunktion heißt konservativ für einen Graphen G, wenn für jeden Zyklus C gilt: c(C) = ∑e∈C c(e) ≥ 0. Es werden daher drei Fälle unterschieden: Gewichtsfunktionen ohne negative Gewichte, konservative Gewichtsfunktionen und Gewichtsfunktionen mit beliebigen Gewichten.

Bei nichtnegativen Gewichten kann Dijkstras Algorithmus das Problem in O(m + n · log(n)) lösen. Dabei bezeichnet m die Anzahl der Kanten und n die Anzahl der Knoten. Bei echt positiven Gewichten stimmen kürzeste Pfade und kürzeste Kantenzüge überein.

Bei beliebigen Gewichten und Kantenzügen ist ein negativer Zyklus entscheidend. Ein negativer Zyklus ist ein Zyklus, dessen Kantengewichtssumme strikt negativ ist. Gibt es einen Weg von s zu diesem Zyklus und von dort zu t, kann der Zyklus beliebig oft durchlaufen werden. Dadurch entstehen Kantenzüge von beliebig kleiner Länge; ein kürzester Kantenzug existiert dann nicht. Der Bellman-Ford-Algorithmus kann in O(nm) einen kürzesten Kantenzug finden, falls einer existiert, oder durch das Finden eines negativen Zyklus nachweisen, dass es keinen gibt. Auch die Frage, ob ein Pfad der Länge ≤ C existiert, lässt sich damit in Polynomialzeit entscheiden.

Bei beliebigen Gewichten und der Beschränkung auf Pfade ist das Problem NP-schwer. Dies folgt beispielsweise durch eine Reduktion vom NP-schweren Hamiltonpfadproblem, indem alle Gewichte auf −1 gesetzt werden. Diese Konstruktion enthält negative Zyklen; deshalb gilt die NP-Schwere in dieser Begründung nicht für konservative Gewichtsfunktionen. Für konservative Gewichtsfunktionen kann Bellman-Ford einen kürzesten Pfad in O(nm) bestimmen. Das Problem des längsten Pfades ist dagegen sogar in ungewichteten Graphen NP-schwer.

Varianten für mehrere Start- und Zielpunkte

Neben der Suche nach einem kürzesten s–t-Pfad gibt es drei eng verwandte Problemvarianten.

Beim Single-source shortest path (SSSP) werden die kürzesten Wege von einem gegebenen Startknoten zu allen übrigen Knoten berechnet. Bei nichtnegativen Gewichtsfunktionen können dafür angepasste Versionen des Dijkstra-Algorithmus oder des A*-Algorithmus verwendet werden. Für beliebige konservative Gewichtsfunktionen berechnet Bellman-Ford stets auch die kürzesten Pfade zu allen anderen erreichbaren Knoten.

Beim Single-destination shortest path (SDSP) sollen die kürzesten Wege von einem gegebenen Endknoten zu allen anderen Knoten bestimmt werden. Dieses Problem lässt sich als SSSP formulieren, indem man die Richtung aller Kanten umkehrt.

Beim All-pairs shortest path (APSP) werden die kürzesten Pfade zwischen allen Knotenpaaren eines Graphen gesucht. Je nach Gewichtsfunktion kann es effizienter sein, für jeden Knoten nacheinander das SSSP-Problem zu lösen. Alternativ gibt es spezialisierte Verfahren wie den Floyd-Warshall-Algorithmus oder den Min-Plus-Matrixmultiplikations-Algorithmus, die die kürzesten Wege für alle Paare gleichzeitig bestimmen.

Typisches Beispiel

Im Beispielgraphen ist ein kürzester Pfad von D nach C der Weg D über B nach C. Seine Kosten betragen 9 + 8 = 17.

Für einen Weg von D nach E ist die direkte Kante mit Kosten 15 dagegen nicht optimal. Der Weg von D über F nach E hat nur Kosten von 14 = 8 + 6 und ist damit der kürzeste der angegebenen Wege.

Lineares Programm

Ein kürzester Pfad kann als Flussproblem formuliert werden. Dazu wird der Pfad als Fluss mit Flusswert 1 auf seinen Kanten interpretiert. Die Bestimmung des kürzesten Pfades ist damit ein Spezialfall des Min-cost-flow-Problems.

Gesucht wird ein Vektor x mit

min ∑e∈E cₑxₑ

unter den Bedingungen

für alle v ∈ V: ∑e∈δ⁻(v) xₑ − ∑e∈δ⁺(v) xₑ = −1, falls v = s; 1, falls v = t; 0, sonst,

und für alle e ∈ E: xₑ ≥ 0.

Die Nebenbedingungen beschreiben den Flusserhalt: Am Startknoten wird eine Einheit Fluss abgegeben, am Zielknoten eine Einheit aufgenommen, und an allen übrigen Knoten bleibt der Fluss ausgeglichen. Existiert ein s–t-Pfad, besitzt das Programm eine zulässige Lösung.

Ist die Gewichtsfunktion nicht konservativ, ist das Programm unbeschränkt, weil der Fluss entlang eines Zyklus mit negativen Kosten beliebig oft erhöht werden kann. Andernfalls besitzt das Programm eine Optimallösung x, die einem 0/1-Vektor mit |E| Einträgen entspricht. Die Kanten mit xₑ = 1 bilden dann einen kürzesten s–t-Pfad; der Zielfunktionswert ist seine Länge.

Knotenpotentiale und weitere Anwendung

Das duale lineare Programm lautet

max yₜ − yₛ

unter der Bedingung für jede Kante e = (u,v) ∈ E:

yᵥ − yᵤ ≤ cₑ.

Eine Lösung y des dualen Programms heißt Knotenpotential. Addiert man zu allen Potentialen denselben Wert δ ∈ ℝ, bleibt die Lösung zulässig. Üblicherweise wählt man δ so, dass yₛ = 0; dann lautet die Zielfunktion max yₜ.

Für jeden Pfad P von s zu einem Knoten w ≠ s gilt:

c(P) = ∑e∈P cₑ ≥ ∑e=(u,v)∈P (yᵥ − yᵤ) = y_w.

Das Potential jedes Knotens ist somit eine untere Schranke für die Länge eines Pfades. Eine Optimallösung erhält man, indem man das Potential y_w jedes Knotens w ≠ s gleich der Länge des kürzesten s–w-Pfades bezüglich c setzt.

Kürzeste-Pfad-Algorithmen werden häufig zur Berechnung von Reiserouten eingesetzt, etwa zur Bestimmung der Entfernung zwischen zwei Städten. Dabei entsprechen die Städte den Knoten und die Straßen den Kanten eines Graphen. Verschiedene Algorithmen sind in der freien Python-Bibliothek NetworkX implementiert.

Eine Erweiterung ist das Constrained Shortest Path Problem. Gesucht wird ein s–t-Pfad P, der zusätzlich die Bedingung ∑e∈P uₑ ≤ U erfüllt. Dabei ist u: E → ℝ₊ eine weitere Gewichtsfunktion und U eine reelle Zahl. Auch bei konservativen oder nichtnegativen Zielfunktionen ist dieses Problem NP-schwer.