Kürzeste Wege finden

Das ganze Leben ist ein Graph.“ – das waren die Worte meines Professors in der Vorlesung zur Graphentheorie. Ganz so einfach ist das Leben dann doch nicht, aber viele Probleme lassen sich tatsächlich mithilfe von Graphenalgorithmen lösen. So auch das Problem des kürzesten Weges. In einem Graphen mit gerichteten und gewichteten Kanten soll der kürzeste Weg zwischen zwei Knoten gefunden werden. Die Gewichtung der Kanten könnte beispielsweise die Entfernung zwischen zwei Orten sein oder auch die Fahrzeit. Gesucht ist dann der Weg mit der kürzesten Strecke oder der geringsten Fahrzeit. Der ­Dijkstra-Algorithmus [1] bietet hierfür ­eine Lösung.