Pfadberechnung

Pfadberechnung bezeichnet das Auffinden eines Pfades zwischen zwei Knoten in einem Graphen. Typische Ziele sind der kürzeste Pfad oder allgemein ein Pfad mit minimalen Kosten, Zeiten oder Entfernungen. Graphen können gerichtet oder ungerichtet, gewichtet oder ungewichtet sein; sie modellieren Netzwerke, Karten oder Raumpläne. In der Robotik und der Logistik ergänzt die Pfadberechnung oft die Pfadplanung, die auch Hindernisse, Dynamik und Ressourcen berücksichtigt.

Wichtige Algorithmen:

Dijkstra findet den kürzesten Pfad in Graphen mit nicht-negativen Kantengewichten; Bellman-Ford funktioniert auch mit negativen Gewichten. Floyd-Warshall berechnet All-Pairs-Pfade. A* nutzt eine Heuristik, um Suchraum zu fokussieren und ist besonders in kartografischen oder Gitter-Umgebungen verbreitet. Johnson-Algorithmus kombiniert Dijkstra mehrmals für All-Pairs; bidirektionale Suche kann Pfade von beiden Endpunkten aus finden und Zeit gewinnen.

Fortgeschrittene Techniken:

Für große oder dynamische Graphen kommen beschleunigende Techniken wie Bidirektionalität, Kontraktionshierarchien oder zeitabhängige Graphen zum Einsatz. In der Robotik und im Spielbereich werden oft auch kontinuierliche Planungsverfahren wie PRM oder RRT eingesetzt, um Pfade in Freiraum zu finden.

Anwendungen und Herausforderungen:

Pfadberechnung findet in Netzwerk Routing, GIS-Karten, Transportplanung, Robotik und Computerspielen Anwendung. Herausforderungen sind negative Zyklen, dynamische Änderungen, Multi-Objektive Ziele und die Realisierung realistischer Kostenmodelle.