Shortest Path Problem

Shortest Path Problem (SPP) ist das Problem, auf einem gewichteten Graphen (gerichtet oder ungerichtet) den Pfad mit minimaler Summe der Kantengewichte zwischen zwei Knoten zu finden, in einer von drei Hauptvarianten: Single-Source-Single-Destination (Punkt zu Punkt), Single-Source-All-Destinations (eine Quelle zu allen Zielen) oder All-Pairs (jedes Paar). Es ist das grundlegende Graphen-OR-Problem; für nicht-negative Kanten ist die kanonische Lösung der polynomiale Algorithmus, den Dijkstra (1959) in einem zweiseitigen *Numerische Mathematik*-Papier definierte (Binary-Heap-Implementierung O((V+E)logV)). Bei negativen Kanten löst Bellman-Ford (Bellman 1958) in O(VE) und erkennt negative Zyklen. Für All-Pairs löst Floyd-Warshall (Floyd 1962) per dynamischer Programmierung in O(V³). Ahuja-Magnanti-Orlin (1993) *Network Flows* ist das kanonische Lehrbuch. Der in der modernen Industrie am häufigsten aufgerufene OR-Algorithmus — er läuft unter Navigationsdiensten, Kartendiensten, Paket-Routing-Protokollen (OSPF), Paket-Liefersequenzierung, Autobahn-Routenplanung; auf landesweiten Straßennetzen liefern moderne vorverarbeitungsbasierte Ansätze (Contraction Hierarchies — Geisberger 2008) Sub-Millisekunden-Anfragezeit. TSP (#068) und VRP (#002) rufen Shortest Path als Subroutine auf, sind aber andere Probleme: Shortest Path ist polynomial, TSP/VRP NP-schwer.