Breitensuche

[GravityDestroyer]

Hallo,
ich habe einen char[][]-Array, welches ein Koordinatensystem darstellt.
Ich habe einen Ausgangspunkt und mehrere Ziele und will nun von allen Pfaden zu den Zielen, den kürzesten Ausgeben.
Gibt es Ideen wie ich so etwas mit dem Breitensuche-Algorithmus implementieren kann?

 

[mihe7]

Ich weiß zwar nicht, was "char[][]-Array, welches ein Koordinatensystem darstellt" zu bedeuten hat, aber mal ganz allgemein und einfach: Du führst für jedes Ziel die Breitensuche aus, bekommst einen Pfad zurück und merkst Dir den kürzesten.

s := Ausgangspunkt
kuerzesterPfad := breitensuche(s, erstes Ziel)

Wiederhole für jedes weitere Ziel z 
    pfad := breitensuche(s, z)
    Falls laenge(pfad) < laenge(kuerzesterPfad)
        kuerzesterPfad := pfad

Gib kuerzesterPfad aus

Natürlich kann man das optimieren, z. B. indem man mit einer einzigen Breitensuche alle Ziele behandelt. Außerdem kann man die Suche beenden, wenn feststeht, dass jeder weitere Pfad nicht kürzer sein kann als der bislang gefundene kürzeste Pfad. Das hängt dann allerdings von der Definition der Pfadlänge ab.

 

[GravityDestroyer]

alles klar, danke

 

[mihe7]

@askanoran Antworten von ChatGPT bitte auch dementsprechend markieren.