Shortest Path (Java)

Jemand ein fertiges Programm?

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Shortest Path (Java)
Ich sitz wieder mal an der Klausuraufgabe von gestern… und versteh dieses Shortest Path Teil nicht. Das steht da so auf den Algo-Folien und stellt sich absolut quer, sobald es in meinen Kopf soll.

Ich hab den Algorithmus mal da rauskopiert, aber dann gesehen, dass der für Adjazenz-Matritzen konzipiert ist. Und da es mir jetzt entschieden zu blöd ist, das Ding auf die geforderten Adjazenz-Listen umzuschreiben (ganz nebenbei ist nicht ausreichend Platz auf der Seite), wollte ich das Prinzip lieber mal von Grund auf verstehen. Leider taugt die Folie dafür so gar nicht.

Am liebsten wär’s mir, wenn jemand ein funktionierendes Java-Programm hat, das mit AdjListen arbeitet. Daran kann ich es wohl am einfachsten verstehen. (Ist doch Java wesentlich besser zum Beschreiben von Algorithmen geeignet als deutsches Gelaber…)


Obs funzt, keine Ahnung:


void shortestPath(int x){
	int MAXVALUE = 999999;
	int s[] = new int[nodes.length];
	for(int i = 0; i < s.length; i++){
		s[i] = -1;
	}
	s[i] = 0;
	int minnode = 0;
	int min = MAXVALUE;
	while(minnode != -1){
		min = MAXVALUE;
		minnode = -1;
		for(int i = 0; i < nodes.length; i++){
			if(s[i] != -1){
				AdjListElement e = nodes[i];
				while(e != null){
					if(s[i] + e.getWeite() < min){
						minnode = e.getNodeNumber();
						min = s[i] + e.getWeite();
					}
					e = e.getNext();
				}
			}
		}
		if(minnode != -1){
			s[minnode] = min;
	}
	for(int i = 0; i < s.length; i++){
		System.out.println("Von " + x + " nach " + i + " : " +s[i]);
	}
}

						

Ich weiss nicht ob das so klappt. Hab da mal ne Frage: Wenn ich ein int-Array erstelle und auf ein bucket zugreife, in dem ich bisher nichts deklariert habe, kommt dann null raus? Wenn nicht bräuchte man noch ein 2. Array, diesmal boolean[] in dem steht, ob der Knoten i in S ist.


In C wird das auf jeden Fall zu unsinnigen Daten oder gar Exceptions führen. In Java kann ich mir vorstellen, dass es auch ne Exception gibt, muss das grad mal ausprobieren.

Ja:
java.lang.ArrayIndexOutOfBoundsException: …

Blöd, dann muss ich meine bisherigen Programme noch etwas anpassen…


meine lösung steht in Let’s Talk Java. Ist aber keine Abwandlung von bisherigen Lösungen, sondern eigener Ansatz. Deswegen auch wieder “ganz anders”. Ich rufe rekursiv durch die Gegend auf.


Und ich habe festgestellt, dass das da oben von mir totaler Käse ist. Kriegs irgendwie nicht zum laufen.


DA IST DAS DING!

Und es funzt…endlich…


	void shortestPath(int x){
		int[] s = new int[nodes.length];
	  	int MAXVALUE = 999999;
	  	for(int i = 0; i < s.length; i++){
	  		s[i] = -1;
	  	}
	  	s[x-1] = 0;
	  	int minnode;
	  	int min;
	  	do{
	  		minnode = -1;
	  		min = MAXVALUE;
	  		for(int i = 0; i < nodes.length; i++){
	  			if(nodes[i] != null && s[i] != -1){
	  				AdjListenElement e = nodes[i];
	  				while(e != null){
	  					if(s[i] + e.getWeite() < min && s[e.getNodeNumber()-1] == -1){
	  						min = s[i] + e.getWeite();
	  						minnode = e.getNodeNumber() - 1;
	  					}
	  					e = e.getNext();
	  				}
	  			}
	  		}
	  		if(minnode >= 0){
	  			s[minnode] = min;
	  			
	  		}
	  	} while (minnode >= 0);
	  	for(int i = 0; i < s.length; i++){
	  	System.out.println("Von " + x + " nach " + (i+1) + " sind es " + s[i]);
		}
	}

Ich check’s net. Bei mir macht es nur Müll… was musst du auch bei 1 anfangen zu zählen??

Hier meine Ausgabe, nachdem ich versucht hab, dem Teil beizubringen, dass Arrays bei 0 anfangen:

(wenn ich es so lass crasht es)


Ich habe die shortestPath Berechnung nach Bellman-Ford (in den Übungsblättern heißt das plötzlich Ford/Fulkerson) gemacht und sieht so aus:

public void shortestPath(int source, int target)
    {
        /* Implementierung von shortestPath nach Bellman-Ford
         * Das Array pathWay[k] speichert die Wegbeschreibung von source
         * zum Knoten k.
         * wayLen[k] speichert die Weglaengen von source bis zum Knoten k
         * Auswahlstrategie ist FIFO
         */

        int len = gEdge.length;
        int iSource = source-1;
        int iTarget = target-1;
        String[] pathWay = new String[len];
        long[] wayLen = new long[len];
        VertexQueue v = new VertexQueue();

        //Initialisierungen
        for(int i = 0; i < wayLen.length;i++) {
            wayLen[i] = 1000000;
            pathWay[i] = new String("");
        }
        v.insert(iSource);
        pathWay[iSource] += "s->";
        wayLen[iSource] = 0L;

        //Beginne Bellman-Ford Algorithmus
        while(!v.isEmpty()) {
            int vertex = v.getVertex();
            if(vertex == iTarget) {
                //String Operationen dienen nur der Wegbeschreibung
                String tString = pathWay[iTarget];
                tString = tString.substring(0,tString.length()-8);
                tString += "->t";
                pathWay[iTarget] = tString;
            } else {
                /* Hole die Liste der Nachbarknoten.
                 * Exisitert ein Verweis auf den Sourceknoten, kann dieser Fall
                 * uebergangen werden. (erstes IF)
                 *
                 * Ist die Weglaenge zum aktuellen Knoten plus die Weglaenge zum
                 * Nachbarknoten kleiner als die schon vorhandene Weglaenge zum
                 * Nachbarknoten, aktualisiere die Weglaenge und die
                 * Wegbeschreibung. Fuege den eben behandelten Nachbarknoten zur
                 * Abarbeitung in die Warteschlange ein. (zweites IF)
                 *
                 * Liegt keiner der beiden Faelle vor, arbeite die Liste der
                 * Nachbarknoten weiter ab.
                 *
                 */
                Edge temp = gEdge[vertex];
                while(temp != null) {
                    int nVertex = temp.getTo()-1;
                    if(nVertex == iSource) {
                       temp = temp.next;
                        continue;
                     } else if(wayLen[vertex] + temp.weight < wayLen[nVertex]) {
                        wayLen[nVertex] = wayLen[vertex] + temp.weight;
                        pathWay[nVertex] = pathWay[vertex] + "v("+(nVertex+1)
                        +")->";
                        v.insert(nVertex);
                        temp = temp.next;
                    } else {
                       temp = temp.next;
                    }
                }
            }
        }
        //Berechnung der kuerzesten Wege beendet, Ergebnis ausgeben.
        System.out.println("Shortest path from " + source + " to " + target +
           ": " + wayLen[iTarget]);
        System.out.println("Way to go: " + pathWay[iTarget]);
    }

Bis jetzt habe ich das nur mit dem Graphen auf Übungsblatt 9 gemacht und damit hat es ganz gut funktioniert.


also ich hab mir jetzt mal grob die 3 implementierungen von fordprefect, str1ch444 und void angeschaut und irgendwie kann ich mich in keinen von denen da richtig reindenken. ich bin mal gespannt wie sowas bei groesseren softwareprojekten im beruf wird - da muss man sich dann wirklich auf schnittstellen einigen und vertrauen, dass das, was dahinter steht, richtig programmiert ist :).

ich hab jetzt jedenfalls auch eine loesung (auf dem blatt papier), von der ich denke, das sie richtig ist und das muss genuegen. meine implementation ist noch etwas naeher am bellman-ford-skript-teil als die von void.


Naja, weil wir das so gut wie in allen Übungsaufgaben so gemacht haben. Aber es umzuschreiben ist ja nicht so schwer. Einfach ein paar mal -1 wegstreichen.


das hab ich gemacht. und zwar da am anfang: (-1 weg)

s[x-1] = 0;

und da am ende: (+1 weg)

System.out.println("Von " + x + " nach " + (i+1) + " sind es " + s[i]);

hab ich was übersehen?

die ausgabe hab ich oben schon beschrieben, das ist so nicht ganz richtig. werd nachher aber mal andere versionen ausprobieren.


Ich denk mal noch die Zeile


if(s[i] + e.getWeite() < min && s[e.getNodeNumber()-1] == -1){

und


minnode = e.getNodeNumber() - 1;

Das müsste es gewesen sein, probiers mal aus.

Und wegen der Ausgabe: liegt auch nur daran, weil er dann den neuen minimalen Weg in den falschen bucket speichert (2.Zeile oben).


schaut gut aus :slight_smile: danke. -1 bedeutet hier wohl ‚nicht erreichbar‘.


Genau, läuft halt alle Knoten/Knoten Kombinationen durch, sucht den kürzesten Weg (der noch nicht in S ist! Wichtig, deshalb hat sich das auch bei mir immer anfangs totgelaufen) und fügt den S hinzu.


also ich weiss ja nicht wirklich, ob die lösungen hier einfacher sein sollen, als meine.
zumindet sind sie vom code her schon mal erheblich umfangreicher. ansonsten halte ich meine lösung noch für sehr effizient :wink:

naja, ich mach mir mal gar nicht erst die mühe, bei dem zeug hier durchzusteigen…


Naja, streich doch die ganzen unnötigen Stringoperationen und Kommentare raus, dann wird’s weniger umfangreich.

Und das Code-Länge nicht zwingend was mit Effizienz zu tun hat, sollte uns spätestens bei den Sortieralgorithmen aufgefallen sein.


Ich glaube nicht, dass der Code für diese Aufgabenstellung effizienter ist. Ganz unabhängig vom Codeumfang.

Aber ich wollte jetzt auch nicht damit anfangen, wer den besseren Code geschrieben hat. Sorry, vergiss meinen Post.


Der ‘bessere Code’ ist in diesem Thread IMHO der, den man besser verstehen kann. Das kann ich noch nicht beurteilen, ich versuch grad, das Verfahren an sich durch Str…'s 2. Version zu verstehen. Und nachdem der das richtige Ergebnis bringt, geh ich davon aus, dass er ‘richtig’ ist…


Str1ch44, kannst du mir dein Prog vielleicht mal etwas genauer beibringen? Ich hab’s jetzt mal etwas umformatiert und mit Kommentaren ausgeschmückt, aber bin irgendwie noch nicht so recht hinter den Sinn des Ganzen gekommen :frowning:

void shortestPath(int x)
{
	int MAXVALUE = 999999;

	int[] s = new int[edges.length];
	for (int i = 0; i < s.length; i++) s[i] = -1;  // Alle Knoten als unerreicht markieren
	s[x] = 0;  // Startknoten ist bereits mit 0 erreichbar

	int minnode;
	int min;
	do
	{
		minnode = -1;
		min = MAXVALUE;
		for (int i = 0; i < edges.length; i++)  // Für alle Knoten (i)
		{
			if (edges[i] != null && s[i] != -1)  // Falls Knoten i Nachfolger hat und noch nicht erreicht wurde
			{
				Edge e = edges[i];
				while (e != null)  // Für alle Nachfolger des Knotens i
				{
					if (s[i] + e.getWeight() < min && s[e.getTo()] == -1)
					// Falls neues Minimum gefunden wurde und Ziel noch nicht erreicht
					{
						min = s[i] + e.getWeight();  // Neues Minimum speichern: s[i] + e.Länge
						minnode = e.getTo();
					}
					e = e.getNext();
				}
			}
		}
		if (minnode > -1) s[minnode] = min;  // Falls minnode gefunden: dessen Länge speichern
	} while (minnode > -1);  // Solange ein minnode gefunden wird

	for (int i = 0; i < s.length; i++)  // Längen für alle Zielknoten anzeigen
		System.out.println("Von " + x + " nach " + i + " sind es " + s[i]);
}