IMP 9 · Algorithmen und Daten
Kürzeste Wege
Ein Navi soll den kürzesten Weg finden. Das Straßennetz ist ein Graph: Knoten sind Orte, Kanten sind Straßen, und jedes Gewicht gibt an, wie lang eine Straße ist. Alle Wege durchzuprobieren dauert viel zu lange. Der Dijkstra-Algorithmus kommt mit wenigen Schritten aus: Er macht immer den offenen Knoten endgültig, der am nächsten am Start liegt, und prüft von dort die Nachbarn.
So gehst du vor
- 1Baue einen Graphen oder nutze das Beispiel. Mit dem Werkzeug „Knoten“ tippst du neue Knoten auf die freie Fläche und ziehst vorhandene herum.
- 2Mit „Kante“ ziehst du von Knoten zu Knoten. Tippe auf ein Gewicht und ändere es rechts.
- 3Wähle Start und Ziel. Der Start hat einen dicken Rand, das Ziel einen zweiten Ring.
- 4Bestimme die nächste Tabellenzeile selbst und prüfe sie dann mit „Schritt“.
Tippe auf „Schritt“, um den Algorithmus zu beginnen.
Orange: Kante wird gerade geprüft. Hell: Kante zum aktuellen Vorgänger. Kräftig: kürzester Weg zum Ziel. Die Schilder an den Knoten zeigen die Entfernung vom Start.
Werkzeug
Start
Ziel
Tabelle des Algorithmus
| Endgültig | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Jede Zeile gehört zu einem Knoten, der endgültig wird. In Klammern steht der Vorgänger. | |||||||
Aufträge
- Bestimme im Beispielgraphen von Hand die kürzeste Entfernung von A zu allen Knoten. Notiere die Tabelle Zeile für Zeile und prüfe sie mit „Schritt“.
- Jemand geht von A aus immer über die kürzeste Kante zu einem noch nicht besuchten Knoten. Welchen Weg geht er? Kommt er in G an?
- Ändere das Gewicht der Kante D – F auf 9. Sage voraus, wie sich der kürzeste Weg nach G ändert, und prüfe mit dem Algorithmus.
- Begründe: Wird ein Knoten ausgewählt, steht seine Entfernung endgültig fest.
- Warum braucht der Algorithmus positive Gewichte? Zeichne auf Papier einen Graphen mit drei Knoten und einer negativen Kante, bei dem er falsch läge.
- Baue einen Graphen mit zwei Knoten, die nicht verbunden sind. Was zeigt die Tabelle? Zähle im Beispielgraphen außerdem, wie viele Kanten der Algorithmus prüft.