PfadAlgorithmen

Pfadalgorithmen sind Verfahren zur Bestimmung von Pfaden in Graphen, insbesondere zur Bestimmung kürzester Wege. Gegeben ist ein gewichteter Graph G=(V,E) mit einer Gewichtsfunktion w: E -> R. Die Distanz d(u,v) bezeichnet die minimale Summe der Gewichte entlang eines Pfades von u nach v. Pfade können Wege ohne wiederholte Knoten sein; in der Praxis werden oft Pfadefehler wie Zyklen vermieden oder genutzt, je nach Problemstellung.

Es gibt verschiedene Problemausrichtungen. Beim Single-Source Shortest Path (SSSP) wird die kürzeste Distanz von einem Startknoten s zu allen anderen Knoten bestimmt. All-Pairs Shortest Path (APSP) liefert die kürzesten Distanzen zwischen allen Knotendauern. Graphen können gerichtet oder ungerichtet, gewichtet oder ungewichtet sein; Gewichte können negativ sein, sofern keine negativen Gewichte Zyklen bilden.

Zu den zentralen Algorithmen gehören der Dijkstra-Algorithmus, der für Graphen mit nichtnegativen Gewichten effizient arbeitet (typischerweise O(m log n) mit Heap-Datenstrukturen). Der Bellman-Ford-Algorithmus behandelt auch negative Gewichte, erkennt negative Zyklen und arbeitet in O(nm). Der Floyd-Warshall-Algorithmus berechnet APSP in O(n^3) und funktioniert auch mit negativen Gewichten, solange keine negativen Zyklen existieren. Der A-Algorithmus ist eine heuristische Erweiterung von Dijkstra, die durch eine admissible Heuristik die Suche beschleunigt. Johnsons Algorithmus kombiniert Reweighting und Dijkstra-Läufe, um APSP in sparsamen Graphen effizient zu ermöglichen.

Anwendungen finden sich in der Routenplanung, Netzwerkrouting, Logistik, Robotik und Computerspielen. Dynamische Varianten adressieren Veränderungen im Graphen, etwa neue Kanten oder Gewichte, und suchen nach inkrementellen oder schnellen Aktualisierungslösungen. Pfadalgorithmen bilden die Grundlage vieler praktischer Optimierungs- und Navigationssysteme.