URL:         /axel/graph_ws0001_blatt3.html
 

Aufgabe 5 - Dijkstra - (4 Punkte)
Beweisen Sie die Korrektheit des Algorithmus von Dijkstra. Tipp: betrachten Sie den entsprechenden Beweis für den Algorithmus von Kruskal.
 

Aufgabe 6 - Union Find (4 Punkte)

In der Vorlesung wurde die Union Find Datenstruktur vorgestellt. Als ein Beispiel soll folgendes dienen:

Betrachte die Primzahlen zwischen 2 und 100. Durchlaufe diese aufsteigend und bilde mittels Union Klassen von Primzahlen mit gleichen Rest modulo 64.
Nun durchlaufe die Repräsentanten dieser  Klassen aufsteigend und fusioniere die Klassen die modulo 32 den gleichen Rest haben. Im nächsten Schritt fusioniere man die Klassen mit gleichen Rest modulo 16, dann die Klassen modulo 8 und zuletzt die Klassen modulo 4. Man fusioniere mit Pfadkompression.