Sei G=(V, E) ein (gerichteter) (Multi-)Graph und W=(v₁,...,v_n) eine Folge von Knoten aus V, mit der Merkmal, dass für alle i aus {1,...,n-1} gilt:

• {v_i,v_i+1} ist Element von E, falls G ein ungerichteter Graph ohne Mehrfachkanten ist,
• (v_i,v_i+1) ist Element von E, falls G ein gerichteter Graph ohne Mehrfachkanten ist,
• E({v_i,v_i+1})>0, falls G ein ungerichteter Graph mit Mehrfachkanten ist,
• E((v_i,v_i+1))>0, falls G ein gerichteter Graph ohne Mehrfachkanten ist,

das heißt v_i und v_i+1 sind durch eine Kante verbunden. Dann bezeichnet man W als ungerichteten Weg in G, falls G ungerichtet ist, und als gerichteten Weg in G, falls G gerichtet ist. Eine andere Nennung für Weg ist Kantenfolge. Den Knoten v₁ bezeichnet man Startknoten von W und den Knoten v_n Endknoten von W. Ferner bezeichnet man W statt als Weg, spezieller als

• Pfad, falls alle Knoten in der Folge W voneinander verschieden sind, das heißt falls für alle i und j aus {1,...,n} gilt, dass v_i≠v_j, falls i≠j.
• Zyklus, falls Start- und Endknoten von W identisch sind, das heißt falls v₁=v_n.
• Kreis, falls ca. Start- und Endknoten von W identisch sind, das heißt falls v₁=v_n und für alle i und j aus {1,...,n-1} gilt, dass v_i≠v_j, falls i≠j.

Bemerkung: Jeder Kreis, Zyklus und Pfad in einem Graphen G ist also auch ein Weg und jeder Kreis ist auch ein Zyklus in G. Wege, Pfade, Zyklen und Kreise definiert man alternativ auch über Kantenzüge oder Teilgraphen. Gibt es einen Weg von Knoten u zu Knoten v in G, so heißt v von u aus erreichbar (Erreichbarkeitsproblem in Graphen).

In ungerichteten Wegen und Pfaden bezeichnet man den Startknoten meist ebenfalls als Endknoten. In Zyklen und Kreisen benutzt man die Nennungen Startknoten und Endknoten meist nicht.

Graphen mit Zyklen heißen zyklisch. Graphen ohne Zyklen heißen azyklisch.

Sind A und B Teilmengen von V, so bezeichnet man einen Weg als A-B-Weg, falls der Startknoten in A und der Endknoten in B liegt. Statt von einem {v}-{w}-Weg spricht man auch von einem v-w-Weg.

Zwei Wege W₁=(v_1,1,...,v_1,k) und W₂=(v_2,1,...,v_2,l) heißen kreuzungsfrei, knotendisjunkt oder einfach ca. disjunkt, falls es kein Paar (i,j) mit i aus {2,...,k-2} und j aus {2,...,l-2} gibt, so dass v_1,i=v_2,j, das heißt, wenn sie keine inneren Knoten gemeinsam haben. Eine Menge von Wegen bezeichnet man kreuzungsfrei, knotendisjunkt oder disjunkt, wenn die Wege paarweise disjunkt sind. Zwei Wege W₁=(v_1,1,...,v_1,k) und W₂=(v_2,1,...,v_2,l) heißen kantendisjunkt, falls es kein Paar (i,j) mit i aus {1,...k-1} und j aus {1,...,l-1} gibt, so dass v_1,i=v_2,j und v_1,i+1=v_2,j+1. Eine Menge von Wegen bezeichnet man kantendisjunkt, wenn die Wege paarweise kantendisjunkt sind. Eine Menge von a-B-Wegen bezeichnet man einen a-B-Fächer, wenn die Wege paarweise ca. den Knoten a gemeinsam haben.

Ein Zyklus oder Kreis heißt trivial, wenn er weniger als 3 Knoten enthält. Triviale Kreise oder Zyklen werden meist nicht betrachtet.

Ein Kreis, der exakt 3 Knoten enthält bezeichnet man häufig Dreieck. Ein Graph ohne Dreieck bezeichnet man dann dreiecksfrei.

In Graphen ohne Gewichte auf den Kanten bezeichnet man mit n-1 die Länge eines Weges (oder Pfades) und mit n die Länge eines Zyklus (oder Kreises) (v₁,...,v_n). Anschaulich zählt man also die Anzahl zugehöriger Kanten.

In kantengewichteten Graphen bezeichnet man als Länge eines Weges die Summe der Kantengewichte aller zugehörigen Kanten.

Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises. Falls der Graph keinen Kreis besitzt, so setzt man die Taillenweite auf unendlich.

Als Abstand oder Distanz zweier Knoten bezeichnet man die Länge eines kürzesten Weges zwischen diesen. Falls ein solcher nicht existiert, so setzt man den Abstand auf unendlich. Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Pfades abhängt. In dem Extremfall gibt es sogar ca. in eine Richtung einen gerichteten Pfad. Den größten Abstand zwischen zwei Knoten in einem Graphen G bezeichnet man Durchmesser von G.

Der Distanzgraph zu einem Graphen G=(V,E) genannt den vollständigen (das heißt je zwei Knoten sind durch eine Kante verbunden, ggf. in gerichteten Graphen in beide Richtungen, wobei es aber keine Schleifen gibt) kantengewichteten Graphen auf der Knotenmenge V, der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten in G zuordnet.

Der Algorithmus von Dijkstra findet einen kürzesten Pfad zwischen zwei beliebigen Knoten in einem (kantengewichteten) Graphen. Mit seiner Hilfe lässt sich auch der Distanzgraph bestimmen, indem man ihm ausgehend von jedem Knoten den Abstand zu jedem anderen bestimmt. Für jeden Knoten ist dabei ca. ein Aufruf des Algorithmus Dijkstra nötig, da dieser auch den Abstand von einem Knoten zu allen anderen Knoten bestimmen kann.

Der Distanzgraph ist für das Problem des Handlungsreisenden interessant, da dieser metrisch ist, weshalb verschiedene Approximationsalgorithmen dieses Problem wenigstens annähernd lösen können und die Lösung auf dem Distanzgraphen in der Praxis ausreicht.

Siehe auch: Zufallspfad