Forum: PC-Programmierung Djikstra Algorithmus


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Kai S. (kai_s7)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Pete K. (pete77)


Bewertung
-1 lesenswert
nicht lesenswert
Hat der Lehrer das nicht erklärt?

von Mikro 7. (mikro77)


Bewertung
1 lesenswert
nicht lesenswert
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?

von Baldrian (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Es heißt Dijkstra-Algorithmus.

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

Dort steht alles für eine Implementierung.

von Yalu X. (yalu) (Moderator)


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

von Mikro 7. (mikro77)


Bewertung
0 lesenswert
nicht lesenswert
Zum ersten Mal vom "Lee-Algorithmus" gehört. ;-)
1
REPEAT
2
     - 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.