Pfadlänge

Pfadlänge bezeichnet in der Graphentheorie die Länge eines Pfades. Ein Pfad P wird typischerweise als Folge von Knoten beschrieben, P = (v0, v1, ..., vk), wobei aufeinanderfolgende Knoten durch Kanten verbunden sind. Die Pfadlänge ist dann gewöhnlich die Anzahl der Kanten im Pfad, also k. In ungewichteten Graphen entspricht die Pfadlänge der Hop-Count, dem Zählen der Schritte.

Bei gewichteten Graphen kann Pfadlänge auch als Summe der Kantengewichte entlang des Pfades definiert werden: Länge_w(P) = w(v0,v1) + w(v1,v2) + ... + w(vk-1,vk). In dieser Definition ist der kürzeste Pfad zwischen zwei Knoten der Pfad mit der geringsten Länge nach der jeweiligen Gewichtung. Ungewichtete Pfadlänge wird oft verwendet, wenn alle Kanten gleiche Kosten haben.

Anwendungen und Algorithmik: Die kürzeste Pfadlänge spielt eine zentrale Rolle in Routing, Netzwerkanalyse und Optimierung. Bekannte Algorithmen zur Bestimmung kürzester Pfade in gewichteten Graphen sind der Dijkstra-Algorithmus, der Bellman-Ford-Algorithmus und der A*-Algorithmus mit passenden Heuristiken. In ungewichteten Graphen kann der BFS-Algorithmus für die Kürzestpfade in Zeit O(m) operieren, wobei m die Anzahl der Kanten ist. Der Begriff Pfadlänge wird auch im Kontext von Distanzen in Netzwerken sowie der durchschnittlichen Pfadlänge (average path length) verwendet.

Varianten: Es gibt Unterschiede zwischen Pfad, Rundweg (geschlossen), Walk, Trail und einfachem Pfad (ohne Wiederholung von Kanten oder Knoten). In gerichteten Graphen wird die Pfadlänge entsprechend der Richtungen der Kanten berechnet. Für unendliche Graphen oder Pfade mit Gewichten gelten Spezialfälle, das grundlegende Konzept bleibt jedoch die Pfadlänge als Maß der Kosten oder der Anzahl der Schritte entlang eines Pfades.