Dijkstra-Algorithmus

Hi,

ich habe mir einen Algo gebaut, der aus einer Distanz(Adjazenz-)-Matrix
den kürzesten Weg von Knoten X nach Y finden soll:

Matrix-Bsp.:
1 2 3 4

1 0 7 6 8
2 5 0 3 9
3 6 8 0 5
4 8 5 7 0

Ausgangsknoten sei Knoten 1.
Der erste Schritt klappt noch ganz gut. Der Weg zu 3 ist am kürzesten und 3
wird markiert. Vorgänger von 3 ist 1. Wenn ich jetzt augehend von 3 die verblei-
benden Knoten 2 und 4 erreichen will (relaxiere...), ist der Weg über 3 länger als der direkte Weg von 1 noch 2 bzw. 1 nach 4. Alle Erläuterungen zum Dijkstra-Algo, die ich gefunden habe, gehen aber davon aus, dass der Weg über
3 zu 2 bzw. 4 kürzer ist als der Weg von 1 nach 2 bzw. 4.
Wie gehe ich in diesem Fall vor. Hab' ich am Algo-Prinzip was falsch verstanden?

Bashar

Dein Graph ist ja voll verbunden, d.h. du kennst am Anfang schon die direkten Kosten von 1 zu 2 und 4. Wenn du jetzt von 3 aus nach 2 und 4 schaust, musst du die sich dadurch ergebenden Kosten mit den schon bekannten Kosten vergleichen und danach entscheiden, ob der kürzeste Pfad von 1 nach 2 bzw. über 3 gehen soll oder nicht.

Hmm, hat denn dann der Algo überhaupt noch einen Vorteil gegenüber der
liniearen Suche ? Im Grunde genommen müsste ich das ja in jedem Schritt
mit jedem möglichen Pfad machen, bis ich alle Knoten mindst. einmal besucht
habe und an meinem Ausgangsknoten wieder angekommen bin. In meinem Beispiel
gibts 6 mögliche Lösungen ((n-1)!), d.h. ich müsste tatsächlich alle möglichen
Pfade bis zum Ende durchlaufen um zu wissen, welcher nun endgültig der
kürzeste ist (?)...

Bashar

Kann ich nicht nachvollziehen. Warum sollte man das tun müssen? Alle möglichen Pfade muss man mit Sicherheit nicht nachvollziehen. In deinem Beispiel bekommst du in Schritt 1 den kürzesten Pfad zu 3, in Schritt 2 den kürzesten Pfad zu 2 und in Schritt 3 den kürzesten Pfad zu 4.

Stimmt. (Übrigens Danke für deine Anworten )
Aber meine Ziel ist es ja, vom Ausgangsknoten 1 ausgehend, in einem Pfad
alle Knoten anzulaufen und wieder zum Ausgangsknoten zurückzukehren. Dabei
will ich den letztlich kürzesten Weg zurücklegen. Zu wissen, wie weit
es vom Start zu jedem einzelnen Knoten ist, reicht also nicht.

Jester

Gast08 schrieb:

Stimmt. (Übrigens Danke für deine Anworten )
Aber meine Ziel ist es ja, vom Ausgangsknoten 1 ausgehend, in einem Pfad
alle Knoten anzulaufen und wieder zum Ausgangsknoten zurückzukehren. Dabei
will ich den letztlich kürzesten Weg zurücklegen. Zu wissen, wie weit
es vom Start zu jedem einzelnen Knoten ist, reicht also nicht.

Du willst also garkein Kürzeste-Wege-Problem lösen (das tut der Dijkstra nämlich) sondern das Problem des Handlungsreisenden (TSP)? Jeden Knoten einmal besuchen und die kürzeste Gesamtstrecke?

Jupp. Ist das nicht nur ein Spezialfall dessen?

Danke. Habe gerade meinen Irrtum selbst bemerkt. Werde mich in Richtung MST-Algo
umsehen. Gibts ja verschiedene - hat jemand eine Empfehlung für Matrizen
bis zu einer Größe von (50,50)?

life

Nimm einfach http://de.wikipedia.org/wiki/Algorithmus_von_Prim.

Allerdings ist MST wieder was anderes als TSP (http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden)

Konrad Rudolph

Hallo,

ist zwar VB.NET, aber der Code ist ganz illustrativ, vielleicht hilft das ja:
http://www.activevb.de/tutorials/tut_antalgo/tut_antalgo.html

C++ Forumbot

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.