Kürzeste Wege

Die Leitprogrammartigen Unterrichtsunterlagen knüpfen an den für die SuS bereits bekannten Begriff des (ungerichteten) Graphen, bestehend aus Knoten und Kanten, an und führen im ersten Kapitel das Konzept eines bewerteten Graphen ein. Anschliessend führen wir den Begriff Distanzgraph ein, womit wir uns auf bewertete Graphen mit positiven Kosten beschränken. Alle nachfolgenden Erläuterungen beziehen sich stets auf zusammenhängende Distanzgraphen. Diese Begriffe legen das Fundament für die Betrachtung verschiedener Optimierungsprobleme und das Konzept eines bewerteten Graphen ist somit der erste zentrale Begriff in diesen LPU. Dadurch können wir nun das Single-Pair-Shortest-Path-Problem (SPSP-Problem) als einen Repräsentanten eines Optimierungsproblems betrachten. In diesem Problem wird der kürzeste Weg zwischen einem gegebenen Paar von Knoten gesucht. Dabei führen wir das Konzept eines Weges als ein Tupel von Knoten ein und zeigen auf, wie man die Länge eines Weges berechnet. Wir definieren nun den kürzesten Weg als einen weiteren zentralen Begriff zwischen zwei Knoten mit Hilfe der Distanz. Wir formalisieren ein Optimierungsproblem abschliessend durch ein 4-Tupel bestehend aus einer Eingabe, der Menge der zulässigen Lösungen, der Bewertungsfunktion sowie dem Optimierungsziel.

Nun sind wir bereit, den Algorithmus von Dijkstra als einen Vertreter eines Graphenalgorithmus, zur Lösung des SPSP-Problems zu besprechen. Der Algorithmus kann ausserdem dazu verwendet werden, um die kürzesten Wege von einem gegebenen Anfangsknoten zu allen anderen Knoten zu ermitteln. Somit können wir auch das SSSP-Problem mit diesem Algorithmus lösen. Weiter gehen wir darauf ein, dass das SPSP-Problem ein Unterproblem für das SSSP-Problem ist. Wir erläutern die grundlegende Idee des Algorithmus mit Hilfe der Berechnung von optimalen Teillösungen. Abschliessend analysieren wir die Korrektheit sowie die Laufzeit des Algorithmus und erläutern das gierige (greedy) Prinzip des Algorithmus.