Pfadlängen

Pfadlängen bezeichnet in der Mathematik und Informatik die Länge von Pfaden in Graphen oder Netzwerken. In ungewichteten Graphen entspricht die Pfadlänge der Anzahl der Kanten, die ein Pfad durchläuft. In gewichteten Graphen hingegen ist die Pfadlänge die Summe der Kantengewichte entlang des Pfades. Welche Kanten gezählt werden, hängt von der gewählten Gewichtung ab; so kann eine Pfadlänge als Kosten- oder Distanzmaß interpretiert werden.

Die Pfadlänge spielt eine zentrale Rolle bei der Bestimmung von Distanzen zwischen Knoten. Die Distanz d(u,v) ist die minimale Pfadlänge zwischen den Knoten u und v. Ein Pfad, dessen Länge der Distanz entspricht, wird als kürzester Pfad bezeichnet. In ungewichteten Graphen lässt sich häufig der kürzeste Pfad mit BFS finden, in gewichteten Graphen mit Algorithmen wie Dijkstra (für nichtnegative Gewichte), Bellman-Ford (auch bei negativen Gewichten) oder dem Floyd-Warshall-Algorithmus für alle Paare.

Eigenschaften der Pfadlängen umfassen Nichtnegativität, und in ungewichteten Graphen die Eigenschaft, dass die Länge eines Pfades mit der Anzahl der Kanten übereinstimmt. Für ungerichtete Graphen ergibt sich oft Symmetrie der Distanz, während in gerichteten Graphen die Dreiecksungleichung d(u,w) ≤ d(u,v) + d(v,w) weiterhin gilt. Die Konzepte lassen sich auch auf geometrische Pfadlängen von Kurven übertragen, wo die Pfadlänge der Bogenlänge entspricht.

Anwendungen finden sich in Netzwerkführung, Routenplanung, Verkehrs- und Logistikoptimierung sowie in Analysen sozialer Netzwerke. Pfadlängen liefern dabei eine abstrakte, meist rechnerische Größe zur Bewertung von Weglängen und Kosten zwischen Knoten in komplexen Systemen.