Next Hop in Disjkstra erkennen?

fb13

Hallo Leute,

Ich habe hier den Dijkstra Algorithmus, der die Distanz von einem Anfangsknoten zu jedem anderen Knoten in einem Graphen ermittelt. Der Code dazu sieht folgendermaßen aus:

for(k = 1; k <= numberOfNodes; ++k){
		mini = -1;
		for(i = 1; i <= numberOfNodes; ++i)
			if(!visited[i] && ((mini == -1) || (distanceSourceToNode[i] < distanceSourceToNode[mini])))
				mini = i;

		visited[mini] = 1;

		for(i = 1; i <= numberOfNodes; ++i)
			if(distance[mini][i])
				if(distanceSourceToNode[mini] + distance[mini][i] < distanceSourceToNode[i]){
					distanceSourceToNode[i] = distanceSourceToNode[mini] + distance[mini][i];
				}
	}

Zur Erklärung des Codes: distanceSourceToNode[i] ist ein Array, der gerade die Distanz zum Knoten i festhält. distance[i][j] dagegen hat die Distanz von Knoten i zu Knoten j.

Dieser Code funktioniert auch. Ich möchte nun aber auch noch speichern, welcher der "Next Hop" zu dem Zielknoten ist. Im Grunde wird ja die Information über die Distanz in der zweiten For- Schleife ständig aktualisiert. Da möchte ich die Information über den Next- Hop auch ständig aktualisieren. Ist das einfach die Variable k, die ich speichern muss oder mache ich einen Denkfehler?

Ich gebe zu, dass dieses Problem eher algorithmisch ist und weniger C bzw. C++ anspricht, aber programmiert ist das Ganze ja in C.

Beste Grüße

mazal

Hallo,

was hindert dich das so wie im Wikipedia-Artikel zu machen

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

D.h. du merkst dir für jeden Knoten den Vorgänger in einem extra int-Array, das für jeden Knoten den Vorgänger im kürzesten Weg speichert. Am Anfang initialisiert alles mit einem INVALID_PREDECESSOR. Dann wird aus der letzten If-Abfrage sowas wie:

if(distanceSourceToNode[mini] + distance[mini][i] < distanceSourceToNode[i]){
  distanceSourceToNode[i] = distanceSourceToNode[mini] + distance[mini][i];
  predecessor[i] = mini;
}

Max3000

Warum schreibst du nicht für deine Node eine Klasse, die Distanz, Nachfolgerknoten und sowas beinhaltet? Da kannst du als Nachfolger einen Pointer zu einem anderem Objekt zu dieser Klasse speichern.

Max3000 schrieb:

Warum schreibst du nicht für deine Node eine Klasse

Huh, was ist denn das?