Pfadproblem

Pfadproblem bezeichnet in der Graphentheorie allgemein eine Klasse von Aufgaben, bei denen es darum geht, einen Pfad zwischen zwei Knoten in einem Graphen zu finden, der bestimmten Kriterien genügt. Typische Domänen sind Informatik, Betriebs- und Ressourcenplanung sowie Robotik; Pfade modellieren Verbindungen, Routen oder Sequenzen in Netzwerken, Karten oder Zustandsgraphen.

Wichtige Varianten sind unter anderem der Pfadexistenztest (gibt es einen Pfad von einem Startknoten s zu einem Zielknoten t?), der Kürzeste Pfad (Pfad mit minimaler Gesamtlänge oder Kosten), der kostengünstigste Pfad bzw. der Pfad mit Nebenbedingungen (z. B. maximale Kosten, maximale Zeit, Kapazitäts- oder Obergrenzen). Weitere Varianten umfassen einfache Pfade ohne Wiederholung von Knoten, Pfade mit Ausschluss von Zyklen, sowie spezielle Probleme wie der Hamiltonsche Pfad, der die Existenz eines Pfads durch alle Knoten einer Graphstruktur fragt. Man unterscheidet zudem zwischen Problemen, die wiederholte Knotenbesuche erlauben, und solchen, die einfache Pfade verlangen.

Komplexität und Lösungsansätze variieren stark. Der Kürzeste Pfad in Graphen mit nicht-negativen Gewichten ist in Polynomialzeit lösbar (zum Beispiel mit Dijkstra). Viele Varianten mit Nebenbedingungen, Bedingungen auf Pfadlänge oder mit Restriktionen gelten als NP-schwer oder NP-vollständig (z. B. Hamiltonpfade, bestimmte konstruierte Nebenbedingungen). In der Praxis kommen oft Heuristiken, A*-Suche, Yen’s Algorithmus oder Eppsteins Algorithmus für k-kürzeste Pfade zum Einsatz; bei großen Instanzen werden auch Approximationen genutzt.

Anwendungen finden sich in Netzwerkrouting, GPS-Navigation, Logistikplanung, Robotik und Schaltungsdesign, wo effiziente oder optimale Pfade entscheidend sind.