Mathematik HTL 4/5, Schulbuch

278 Diskrete Mathematik Gegeben ist ein bewerteter Graph G und eine Ecke a von G. Die Bewertungen der Kanten sind nicht negativ, wir interpretieren sie vorläufig als „Weglängen“. (Es könnte sich aber genauso um die für diesen Weg erforderliche Zeit, die Kosten oder ähnliches handeln.) Wir wollen den Baum der kürzesten Wege mit Ausgangspunkt a ermitteln und verwenden dazu den Algorithmus von Dijkstra: Zunächst besteht unser Baum nur aus der Eckenmenge E a = {a} und der leeren Kantenmenge K a = { }. Die folgenden Anweisungen werden so lange ausgeführt, bis E a alle Ecken von G enthält:  Wähle alle Ecken von G, die noch nicht zum Baum gehören und die direkt über eine einzelne Kante von einer beliebigen Ecke aus E a erreichbar sind. Bestimme zu jedem dieser Punkte alle möglichen Weglängen, die von a aus zu diesem Punkt führen und bei denen alle bis auf die letzte Kante aus K a stammen.  Wähle aus allen so bestimmten Wegen einen mit kürzester Länge aus.  Füge den Endpunkt dieses Weges zu E a hinzu und seine letzte Kante zu K a .  Wenn E a = E ist, so ist der Algorithmus beendet, ansonsten wiederhole die hier angegebenen Schritte. Tipp Es ist sinnvoll, zu jeder neu zum Baum hinzugefügten Ecke gleich die Entfernung vom Ausgangs- punkt zu notieren, damit man mit der Weglängenberechnung nicht in jedem Schritt von Anfang an neu beginnen muss. 1065 Das Straßennetz einer Ortschaft ist durch einen Graphen gegeben. a. Ermittle mithilfe des Algorithmus von Dijkstra den Baum der kürzesten Wege mit Ausgangspunkt a. b. Gib den kürzesten Weg von a nach h an. a.  Wir beginnen in der Ecke a. Die a nächstgelegene Ecke ist c, mit der Entfernung 1. Wir notieren neben der Ecke c die Entfernung 1. Es ist E a = {a, c} und K a = {[a, c]}.  Jetzt betrachten wir alle Ecken, die von a oder c auf direktem Wege erreichbar sind: Das sind die Ecken b, d und i. Die infrage kommenden Wege haben die Längen 1,2 (von a direkt nach b), 2,5 (von a direkt nach d), 2,3 (von a über c nach d) und 3,5 (von a über c nach i). Da der kürzeste dieser Wege die Länge 1,2 hat und in der Ecke b endet, notieren wir neben b die Entfernung 1,2 und verändern E a zu E a = {a, b, c} und K a zu K a = {[a, b], [a, c]}. Algorithmus von Dijkstra a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1,3 1 2,5 1,4 2 0,5 einen kürzesten Weg bestimmen A, B a b e f h g d i c 1,2 1,7 2 1,7 3 1,9 2 2,5 1,3 1 2,5 1,4 2 0,5 1 1,2 a b e f h g d i c 1,7 2 1,7 3 1,9 2 2,5 1,3 1 2,5 1,4 2 0,5 1 1,2 Nur zu Prüfzwecken – Eigentum des Verlags öbv