Djikstra Algorithmus

[Kai S. (kai_s7)]

Hallo,
ich möchte ein Programm schreiben, der eine 2D-Matrix (Start = 1; Ziel: 
0; Platz: 2; Hinderniss: -1) als Input nimmt und nach dem Djikstra 
Algorithmus die optimale Route berechnet und als Output einen 
2x1-Matrix ausgibt mit dem optimalen Weg.
Das Programm möchte ich mit MATLAB nutzen.

Es gibt viele Dateien im Internet, jedoch nutzen alle Knoten und einen 
Graphen. Wenn ich beispielsweise einen Code mit Matrizen finde, dann ist 
der mit verschiedenen Zahlen beschriftet.

Nun zu meiner Frage:
Wie genau kann ich den Code umschreiben, um den gewünschten Input, 
Output zu bekommen und die gewünschte Matrix zu verwenden.

Danke.

[Pete K. (pete77)]

Hat der Lehrer das nicht erklärt?

[Mikro 7. (mikro77)]

Kai S. schrieb:
> Wie genau kann ich den Code umschreiben, um den gewünschten Input,
> Output zu bekommen und die gewünschte Matrix zu verwenden.

Ein Graph besteht aus Knoten und Kanten.

Angenommen: In einer Matrix sind die indizierten Elemente die Knoten; 
die Kanten sind die Übergänge zu den Nachbarelementen. Dann wäre die 
Transformation von der Matrix zum Graphen einfach, richtig?

In deiner Matrix sind hingegen nur diejenigen Elemente auch Knoten, die 
mit 0,1,2 markiert sind. Wie sieht hier dein Lösungsansatz aus?

[Baldrian (Gast)]

Es heißt Dijkstra-Algorithmus.

https://de.wikipedia.org/wiki/Dijkstra-Algorithmus

Dort steht alles für eine Implementierung.

[Yalu X. (yalu) (Moderator)]

Die Spezialisierung des Dijkstra-Agorithmus auf Gittergraphen heißt
Lee-Algorithmus. Unter diesem Begriff findest du mehr.

[Mikro 7. (mikro77)]

Zum ersten Mal vom "Lee-Algorithmus" gehört. ;-)

REPEAT
     - Mark all unlabeled neighbors of points marked with i with i+1

Da geht irgendwo verloren, dass man (genauso wie bei der Breitensuche) 
eine Queue benötigt, in der man die Trackingpoints speichert (oder man 
erhöht die Komplexität "etwas" und durchsucht in jedem Durchgang alle 
Elemente ;-).

Wenn es wirklich um ein Maze geht, wird man aber sowieso besser von 
beiden Enden aus suchen (falls Komplexität wichtig sein sollte).

Soll es allgemein sein (also Dijkstra wie vom TS geschrieben) dann kann 
man solche Matrix-Elemente mit lediglich zwei Nachbarn als Teil einer 
gewichteten Kante betrachten, was die Knotenmenge erheblich reduzieren 
kann.

Führt aber alles wohl zu weit: Ich haben den Eindruck der TS ist noch 
dabei sich mit dem Konzept Graph/Knoten/Kanten vertraut zu machen.