Das Pro­blem des kür­zes­ten Weges – Di­jk­s­tra und die Amei­sen

Wege in Gra­phen

Auf­ga­be

1. 1. Wel­ches ist der kür­zes­te Weg von Als­dorf nach Fah­ren­dorf?

   2. Wie kannst du si­cher sein, dass es kei­nen kür­ze­ren Weg gibt?

      

2. Was wäre ein 'si­che­res' Vor­ge­hen, um zwei­fels­frei den kür­zes­ten Weg zu fin­den?

3. Wie viele sol­cher Wege gibt es, die bei A be­gin­nen, bei Z enden und jeden Kno­ten höchs­tens ein­mal be­su­chen? Wir gehen vom schlech­tes­ten Fall aus, näm­lich dass jeder Kno­ten mit jedem ver­bun­den ist.

   

4. Er­gän­ze die Amei­sen­re­geln:

   

5. 1. Si­mu­lie­re wie die Amei­sen lau­fen. No­tie­re je­weils den Zu­stand nach 6, 7, 9, ... Mi­nu­ten.

      

   2. Wel­ches ist der kür­zes­te Weg?

   3. Wieso kannst du si­cher sein, dass es kei­nen kür­ze­ren Weg gibt?

   4. Wenn es in einem Gra­phen zwei gleich lange, kür­zes­te Wege gibt, wel­chen wür­den die Amei­sen fin­den? Über­le­ge dir dazu ein Bei­spiel.

Das Pro­blem des kür­zes­ten Weges – Di­jk­s­tra und die Amei­sen: Her­un­ter­la­den [odt][1 MB]

Das Pro­blem des kür­zes­ten Weges – Di­jk­s­tra und die Amei­sen: Her­un­ter­la­den [pdf][523 KB]

Wei­ter zu Der Di­jk­s­tra Al­go­rith­mus