Graphendurchlauf

Wissenschaft Informatik
#1

Hallo!

Ich möchte ein Programm erstellen, das den kürzesten Weg durch einen Graphen findet:

Dem Programm wird ein bestimmer Punkt A vorgegeben. Das Programm soll nun in einer möglichst kurzen Laufzeit den kürzesten Weg durch den Graphen zurück zu A finden, sodass alle Kanten oder Knoten mindestens einmal durchlaufen wurden.

Ich kenne bisher nur einen Algorithmus, der die kürzeste Entfernung von einem Punkt A zu einem Punkt B ermitteln können (Dijkstra).

Außerdem habe ich mir selbst schon Gedanken darüber gemacht, wie ein solcher Algorithmus laufen müsste, aber leider komme ich dabei auf eine theoretisch unendliche Laufzeit und finde dabei keine Abhilfe.

Ich hoffe es kann mir jemand bei diesem Problem weiterhelfen. Für Hilfe wäre ich sehr dankbar.

Mit freundlichen Grüßen,
fuenf_punkt_eins

#2

Hi,

das Traveling-Salesman-Problem und seine Komplexität sind Dir bekannt?

Die andere Variante hat wohl was mit Hamilton-Kreisen zu tun, auch kein leichtes Problem.

Gruß, Lutz

#3

Nein, tut mir Leid, die sind mir beide nicht bekannt. Aber danke für die Hinweise. Ich werde mir beide Probleme mal ansehen, nach Lösungsansätzen suchen und versuchen, diese in mein Problem mit einzubringen. Nach dem, was ich jetzt gerade darüber gelesen habe, klingt es nach genau dem Richtigen, wonach ich suche.
Herzlichen Dank für die Tipps! :smile: