Projekt:Mathematik in Natur und Technik/dijkstra/Lösungen

Lösung zu Aufgabe 1:

1. Durchlauf:

- Initialisiere den Startknoten (Karslruhe) mit 0 und alle anderen Knoten mit ∞. Weise den Nachbarknoten (Heidelberg, Hockenheim, Philippsburg) die Eigenschaften Distanz (Entfernung) und Vorgänger zu.

2.Durchlauf

- Suche den Knoten, der die minimalste Distanz zum Startpunkt hat mit Hilfe der Prioritätsschlange (Philippsburg). (aus Front)

- Speichere, dass dieser Knoten besucht wurde.

- Berechne für alle neuen Nachbarknoten die Distanz zum Startpunkt (Speyer = 65,8).

- Der Knoten ist „neu“ und hat keinen Vorgänger: Die Werte (Vorgänger und Entfernung) werden gespeichert.

3.Durchlauf

- Suche den Knoten, der die minimalste Distanz zum Startpunkt hat mit Hilfe der Prioritätsschlange (Heidelberg). (aus Front)

- Speichere, dass dieser Knoten besucht wurde.

- Berechne für alle neuen Nachbarknoten (Mannheim) die Distanz zum Startpunkt (Mannheim = 66,4).

- Der Knoten ist „neu“ und hat keinen Vorgänger: Die Werte (Vorgänger und Entfernung) werden gespeichert.

4.Durchlauf

- Suche den Knoten, der die minimalste Distanz zum Startpunkt hat mit Hilfe der Prioritätsschlange (Hockenheim). (aus Front)

- Speichere, dass dieser Knoten besucht wurde.

- Berechne für alle neuen Nachbarknoten (Mannheim) die Distanz zum Startpunkt (Mannheim = 74,3).

- Der Knoten ist schon bekannt und hat somit einen Vorgänger.

- Der aktuelle Weg ist länger: Werte bleiben erhalten.

5.Durchlauf

- Suche den Knoten, der die minimalste Distanz zum Startpunkt hat mit Hilfe der Prioritätsschlange (Speyer). (aus Front)

- Speichere, dass dieser Knoten besucht wurde.

- Berechne für alle neuen Nachbarknoten (Mannheim) die Distanz zum Startpunkt (Mannheim = 90).

- Der aktuelle Weg ist länger: Werte bleiben erhalten.

6.Durchlauf

- Suche den Knoten, der die minimalste Distanz zum Startpunkt hat mit Hilfe der Prioritätsschlange (Mannheim). (aus Front)

- Speichere, dass dieser Knoten besucht wurde.

Ich hoffe ihr konntet hier sehen, wie der Algorithmus anzuwenden ist. Nun könnt ihr euch, wenn ihr wollt, an der 2. Aufgabe versuchen.

Lösung zu Aufgabe 2: