Kürzeste Wege mit Dijkstra

Folgende Schritte werden wiederholt, solange das Ziel noch nicht erreicht wurde:

1.Wähle den Knoten mit der kürzesten Distanz.
2.Berechne alle nebenliegenden Entfernungen neu
3.Aktualisiere die Tabelle.
4.Markiere den Knoten als fertig.
Präsentation

Umsetzung mit Scratch

Umsetzung mit Sratch wird mit Hilfe von zwei Listen gemacht. Damit die Entfernung, die hier nur eine Zahl zwischen 0 und 98 sein darf, immer aus 3 Ziffern besteht, wird einfach 100 dazu addiert. 

Entfernung Codierung
0 100
14 114
unendlich 199

Genauso macht man es mit den Koordinaten. Da diese positiv oder negativ sein können und die Ziffernanzahl variieren kann, wird einfach zur Koordinate 500 addiert, so erhält man für jede  Koordinate eine dreistellige Zahl, diese kann man scratch ausgelesen werden.

 

 

Eingabe der Entfernungsliste

Die Listen werden zunächst durch Anklicken und Eingabe der entfernungen erstellt.

Hierbei gibt es immer nur 6 Orte, die Entfernungen sind zwischen 1 und 9. Intern werden die Listen aktualisiert, mit diesen dann der Algorithmus rechnet.

Algorithmus

Anhand der Listen berechnet der Algorithmus den kürzesten Weg. Anhand der Ergebnisliste kann der kürzeste Weg durch sukzesiven Suchen des Vorgängers rekonstruiert werden. Hier kann der Stift diesen Weg abfahren und kenzeichnen.

Umsetzung

Scratch Quelldatei

Dijikstra_V10.sb2 (100,0 KiB)

Zurück