Floyd Warshal Algo

[Krikus]

Hi,

ich habe hier eine Methode, auf Basis des Floyd-Warshall Algos.
Dieser klappt auch soweit,
Nun soll aber neben der kürzesten Distanz, noch der Weg ausgegeben werden, der gefahren wird.

z.Z gibt er mir alle Orte aus, welche er im Zuge der Berechnung des kürzesten Weges besucht aus.
Aber das er mir den Weg ausgibt, den man fahren muss, um die kürzeste route zu nehmen bekomme ich nicht hin.

	double Floyd2(string x, string y)  //Übergabe x=start_ort y=ziel:ort
	{
		int v = consist_of(x);
		int w = consist_of(y);
		string weg = "";

		if(v != -1 && w != -1)
		{
			const double infinit = numeric_limits<double>::infinity();           // (MAXFLOAT = unendlich) HUGE_VAL
			double *C = new double[vertex.size()*vertex.size()];  // Kostenmatrix
			for (int i=0; i<vertex.size(); i++)            // Kostenmatrix initialisieren
				for (int j=0; j<vertex.size(); j++)          
					if (IsArc(i,j))
						C[i*vertex.size()+j] = GetArc(i,j);// C[i,j] mit Kantengew. belegen
					else
						C[i*vertex.size()+j] = infinit;      // C[i,j] mit unendlich belegen
		                        
			for (int i=0; i<vertex.size(); i++)            // Kostenmatrix initialisieren
				for (int j=0; j<vertex.size(); j++)          
					if (i == j ) C[i*vertex.size()+j] = 0;    // C[i,i] = 0
			for (int k=0; k<vertex.size(); k++)          
				for (int i=0; i<vertex.size(); i++)          
					for (int j=0; j<vertex.size(); j++)
						if (C[i*vertex.size()+j] > C[i*vertex.size()+k] + C[k*vertex.size()+j])
						{     //weg zusammen setzten
							if(vertex[k].visited == false)
							{
								weg+= vertex[k].value+ " ";

								vertex[j].visited = true;
							}



							C[i*vertex.size()+j] = C[i*vertex.size()+k] + C[k*vertex.size()+j];
						}

			for(int i=0;i<vertex.size();i++) //Konten wieder auf visited = false setzten
			{
				vertex[i].visited = false;
			}
//überprüfen ob es überhaupt einen Weg gibt
			if(C[v*vertex.size()+w] != numeric_limits<double>::infinity())
			{
				cout << weg <<endl;
				return C[v*vertex.size()+w];
			}
			else
				return -1;
		}
		return -1;
	
	}

 

[Matthias Reitinger]

Hallo Krikus,

um den kürzesten Weg zu ermitteln, könntest du dir eine zusätzliche n*n-Matrix definieren, die an der Stelle (i,j) den jeweils momentan bekannten kürzesten Weg zwischen Knoten i und Knoten j speichert. Wenn du im Floyd-Warshall-Algorithmus dann einen kürzeren Weg zwischen i und j über k gefunden hast, setzt du den Weg von i nach j auf die Konkatenation des Weg zwischen i und k und des Weges zwischen k und j. Wie man diese Wegematrix initialisiert, kann man sich leicht überlegen.

Grüße,
Matthias

 

[Krikus]

Ich hab es einmal modifiziert:

if(i==v && j == w)
{
//weg+=vertex[k].value+ " ";	
cout << i << " nach " << k << " ---- " << k << " nach " << j << endl; 
}

Bei einem Ort als Zwischenstation klappt es nun.
Bei mehr als 2 Orten leider noch nicht..

 

[Matthias Reitinger]

Ich hab es einmal modifiziert:

if(i==v && j == w)
{
//weg+=vertex[k].value+ " ";	
cout << i << " nach " << k << " ---- " << k << " nach " << j << endl; 
}

Damit bekommst du zumindest schon einmal mit, wenn ein neuer, kürzerer Weg von v nach w gefunden wurde. Du weißt damit aber nur, dass der Weg über k läuft. Wenn du den kompletten Weg haben willst, musst du dir eben entsprechend die Wege für alle Paare von Knoten speichern, wie ich ja schon in meinem letzten Beitrag erläutert hatte.

Grüße, Matthias

P.S.: Den Floyd-Warshall-Algorithmus verwendet man in der Regel nicht, wenn man lediglich am kürzesten Weg zwischen zwei Knoten interessiert ist (der Algorithmus berechnet nämlich noch viel mehr, nämlich die kürzesten Wege zwischen allen Knotenpaaren). Der Dijkstra-Algorithmus wäre hier eine bessere Wahl.

 

[Krikus]

Meinst du sowas hier?

if (C[i*vertex.size()+j] > C[i*vertex.size()+k] + C[k*vertex.size()+j])
{

	test[i][j]+=vertex[i].value + " nach " + vertex[k].value + " ---- " + vertex[k].value + " nach " + vertex[j].value;
     C[i*vertex.size()+j] = C[i*vertex.size()+k] + C[k*vertex.size()+j];
}

Bei der Ausgabe von test[v][w]; bleibt der Weg gleich dem obigen Code.

 

[Matthias Reitinger]

Meinst du sowas hier?

if (C[i*vertex.size()+j] > C[i*vertex.size()+k] + C[k*vertex.size()+j])
{

	test[i][j]+=vertex[i].value + " nach " + vertex[k].value + " ---- " + vertex[k].value + " nach " + vertex[j].value;
     C[i*vertex.size()+j] = C[i*vertex.size()+k] + C[k*vertex.size()+j];
}

Nicht ganz. Die Aktualisierung sollte eher so aussehen:

test[i][j] = test[i][k] + test[k][j]

Der neue Weg von i nach j ist ja der Weg von i nach k, gefolgt vom Weg von k nach j.

Grüße, Matthias