Kürzeste Wege – Graphen und Graphentheorie

Definition des Kürzesten Weges

Ein kürzester Weg in einen Graphen entspricht einem Weg von s (start) nach t (terminate) mit minimalen Gesamtkosten. Hierbei sind die Gesamtkosten die Summe der verwendeten Kantenkosten, also der Distanz von s nach t: d(s, t). Die Knoten s und t entstammen der Knotenmenge V aus dem Graphen G = (V, E). 

Eine Definition über Graphen und dessen Bestandteile können im Blogpost über Graphen nachgelesen werden. 

Problemfälle bei kürzesten Wegen

Wenn die Kantenkosten negativ sind, können Kreise entstehen. Diese können einige Algorithmen nicht lösen, wodurch die Rechenzeit unendlich beträgt und die Lösung nicht dem kürzesten Weg entspricht. Auch können einige Algorithmen (zum Beispiel der Algorithmus von Dijkstra) aufgrund gewisser Graphenstrukturen nicht den kürzesten Weg finden.

Algorithmen für kürzeste Wege

Algorithmus von Dijkstra

Dieser Algorithmus benützt eine sogenannte Front Strategie. Dies bedeutet, dass er in jedem Schritt einen weiteren Knoten von den nicht bereits in der Liste als „fertig“ gespeicherten Konten hinzufügt. Dabei verlässt sich der Algorithmus auch auf die Dreiecksungleichung. 

Algorithmus von Floyd-Warshall 

Praktische Anwendungen

Das kürzeste Wege Problem findet vor allem Anwendung in der Navigationstechnik. Hierbei wird meist der kürzeste oder schnellste Weg zwischen zwei Orten (Adressen) gesucht, wobei das Kantengewicht entweder die Kilometer oder die Geschwindigkeit entsprechen kann. Zur Vereinfachungen werden in der praktischen Anwendung Portale benützt. Diese Portale umfassen zum Beispiel gesamte Hauptstädte. Aus den Portalen gibt es lediglich wenige Ausfahrtsrouten, meist Fernstraßen sowie Autobahnen. Zudem gibt es eine Tabelle mit allen Entfernungen zwischen jeder der einzelnen Portalsausfahrten zu den Portalsausfahrten einer anderer Stadt (n-zu-n Beziehung). Dadurch besteht die Routenberechnung lediglich aus drei Teilen: 

1. Route zwischen (Start-)Adresse und ausgewählten Ausfahrtsportal in Stadt A in Punkt 2
2. Auswahl der schnellsten Strecke, also Auswahl von Ausfahrtsportal Stadt A sowie Einfahrtsportal Stadt B aufgrund der kürzesten Strecke, geringsten Geschwindigkeit, etc. 
3. Route zwischen Einfahrtsportal in Stadt B sowie der (Ziel-)Adresse