Flo Teil

2 Kürzeste Wege in bewerteten Graphen

Übung 2.1

Führen Sie den Dijkstra-Algorithmus per Hand für folgende Graphendarstellung aus. Legen Sie dazu eine Tabelle an.

Übung 2.2

Implementieren Sie den Floyd-Algorithmus in einer Programmiersprache Ihrer Wahl. Lesen Sie dazu eine Matrix ein (alternativ: im Quelltext hardcoden) und wenden Sie den Algorithmus an. Geben Sie die Ergebnismatrix aus. Testen Sie ihren Algorithmus mit folgenden Matrizen:

Übung 2.3

Machen Sie sich selbststädnig mit verschiedenen Speicherstrukturen und ihren Vor-/Nachteilen für die verschiedenen Algorithmen vertraut. (Bsp. Fibonacci-Heap)

Übung 2.4

Machen Sie sich mit weiteren Algorithmen zur Bestimmung des kürzesten Weges vertraut. Welche Unterschiede weisen diese auf? (Bsp. A*-Algorithmus, Bellman-Ford-Algorithmus)