Das Problem des kürzesten Weges – Dijkstra und die Ameisen

Wege in Graphen

Aufgabe

1. 1. Welches ist der kürzeste Weg von Alsdorf nach Fahrendorf?

   2. Wie kannst du sicher sein, dass es keinen kürzeren Weg gibt?

      

2. Was wäre ein 'sicheres' Vorgehen, um zweifelsfrei den kürzesten Weg zu finden?

3. Wie viele solcher Wege gibt es, die bei A beginnen, bei Z enden und jeden Knoten höchstens einmal besuchen? Wir gehen vom schlechtesten Fall aus, nämlich dass jeder Knoten mit jedem verbunden ist.

   

4. Ergänze die Ameisenregeln:

   

5. 1. Simuliere wie die Ameisen laufen. Notiere jeweils den Zustand nach 6, 7, 9, ... Minuten.

      

   2. Welches ist der kürzeste Weg?

   3. Wieso kannst du sicher sein, dass es keinen kürzeren Weg gibt?

   4. Wenn es in einem Graphen zwei gleich lange, kürzeste Wege gibt, welchen würden die Ameisen finden? Überlege dir dazu ein Beispiel.

Das Problem des kürzesten Weges – Dijkstra und die Ameisen: Herunterladen [odt][1 MB]

Das Problem des kürzesten Weges – Dijkstra und die Ameisen: Herunterladen [pdf][523 KB]

Weiter zu Der Dijkstra Algorithmus