Pfadvektoren

Pfadvektoren bezeichnet in der Informatik und Mathematik Vektoren, die einen Pfad in einem Graphen oder Netzwerk eindeutig beschreiben. Ein Pfad von Knoten von v0 zu vk kann durch die geordnete Sequenz der Knoten oder durch die Sequenz der Edges dargestellt werden. Pfadvektoren dienen der Speicherung, dem Vergleich und der rekonstruktiven Pfadbestimmung in Algorithmen. Häufig werden Pfade durch Start- und Endpunkt sowie eine Liste der Zwischenknoten oder Kanten beschrieben. In gewichteten Graphen können Pfadvektoren zusätzlich mit Kosten versehen werden, sodass Pfade nach Gesamtkosten sortiert oder ausgewählt werden können.

Im Bereich der Netzwerktechnik bezeichnet Pfadvektor-Routing oft das Pfadvektor-Verfahren. Updates tragen die vollständige Pfadsequenz von der Quelle zum Ziel, typischerweise als Sequenz von autonomen Systemen (AS-Pfad). Vorteile sind policy-basiertes Routing und Schleifenvermeidung; Nachteile können größerer Overhead und Skalierungsprobleme in großen Netzen sein. Das bekannteste Beispiel ist das Border Gateway Protocol (BGP), das Pfadvektor-Informationen nutzt, um Routing-Entscheidungen zu treffen.

Varianten der Repräsentation umfassen Sequenzen von Knoten-IDs, Edges oder binäre Vektorformen, die die Zugehörigkeit zu Pfaden codieren. Die Wahl der Darstellung beeinflusst Speicherbedarf und Effizienz von Pfadsuchen und Pfadvergleichen. Pfadvektoren ermöglichen damit sowohl algorithmische Pfadkritik als auch praktikable Implementierungen in Netzwerken.