Als Distanz oder Abstand zweier Knoten in einem Graph bezeichnet man die Länge eines kürzesten Pfades zwischen diesen. Falls ein solcher Pfad nicht existiert, so setzt man den Abstand auf unendlich. Der Abstand eines Knoten zu sich selbst ist Null.

Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Pfades abhängt. Dabei kann es sogar vorkommen, dass ein endlicher Abstand nur in eine Richtung existiert.

Die Ermittlung des kürzesten Abstands zweier Knoten ist zum Beispiel für Routenplaner wichtig. Er lässt sich auf einfache Weise mit dem Algorithmus von Dijkstra berechnen.

Aus den paarweisen Distanzen aller Knoten eines Graphen lässt sich der Distanzgraph konstruieren.

Beispiele

Ein Beispiel für den Abstand in Graphen ist der Abstand zweier Personen in Sozialen Netzwerken. Dabei werden die Personen als Knoten repräsentiert, zwischen denen jeweils eine Kante existiert wenn sie einander kennen oder durch eine andere Eigenschaft miteinander verbunden sind (siehe dazu auch das Small World Phänomen und die Erdös-Zahl).