Ameisen

nach Jens Gallenbacher: Abenteuer Informatik

Ameisen

Die Ameisen starten gleichzeitig im Startknoten. In alle Richtungen schwärmen sie gleich schnell aus:

Erreichen Ameisen einen ersten Nachbarknoten, so teilen sie sich sogleich und folgen allen weiteren Verzweigungen, immer noch im genau gleichen Tempo.

Dasselbe passiert nun bei verschiednen Knoten. Teilweise marschieren Ameisen auf der selben Kante aufeinander zu.

Treffen sich aus unterschiedlicher Richtung kommende Ameisen auf einer Kante, so wird diese Kante entfernt: Man weiss dass die beiden Knoten, von wo die Ameisen aus auf diese Kante gekommen sind, bereits entdeckt sind.

So geht das Entdecken weiter: Bei neuen Knoten teilen sich die Ameisen, bei Kanten begegnen sie sich.

Schlussendlich ist jeder Knoten von Ameisen entdeckt worden. Und zwar immer auf dem schnellsten Weg vom Startknoten aus. Wenn wir die nicht-durchgestrichenen Kanten zurück zum Start verfolgen, haben wir also den schnellsten Weg gefunden.