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 Way (26.03.2002)
Hi
Ich wurde gebeten, meine Lösung dieser Aufgabe hier zu posten.
Es geht darum, den kürzesten Weg zu finden, wobei die Wege in verketten Listen und nicht in einem Array gespeichert sind. Somit muss man ganz anders vorgehen, als wenn man einen Array hätte.
Also hier der tolle Code:
/* Diese Klasse beschreibt einen Weg/Edge von einem best. Punkt aus und ist Element einer verketteten Liste */
public class Edge {
int POP, way;
Edge nextone;
Edge (int POPto, int wayto, Edge next) {
POP = POPto; way = wayto; nextone = next;
}
void addEdge (int to, int wayto) {
if (nextone == null) nextone = new Edge(to, wayto, null);
else nextone.addEdge(to, wayto);
}
void waycalc (int[] ways, POP[] pops, int tillnow, int iself) {
pops[POP].waycalc(ways, pops, tillnow + way, POP);
if (nextone != null) nextone.waycalc(ways, pops, tillnow, iself);
// System.out.println("I'm from " + iself + " and will go to " + POP + " therefor I need " + way);
}
}
/* Hier haben wir nun die Wegpunktklasse. Firstone ist dann das erste Element der Wegliste. POP steht fuer Point Of Presence ;) */
public class POP {
Edge firstone;
POP() {
firstone = null;
}
void addEdge (int to, int wayto) {
if (firstone == null) firstone = new Edge(to, wayto, null);
else firstone.addEdge(to, wayto);
}
void waycalc (int[] ways, POP[] pops, int tillnow, int iself) {
if (tillnow == -1) { if (firstone != null) firstone.waycalc(ways, pops, 0, iself);
} else {
if ((ways[iself] == 0)||(ways[iself] > tillnow)) {
ways[iself] = tillnow;
if (firstone != null) firstone.waycalc(ways, pops, tillnow, iself);
}
}
// System.out.println("I am " + iself + " and I needed " + tillnow);
}
}
/* Und nun kommen wir zum Kopf des Ganzen. In Main habe ich Beispielwege fuer 15 Punkte angelegt. Diese sind aus einem Buch (der Code natuerlich nicht ;), in dem uebrigens eine Loesung fuer die Arraymethode steht. */
public class AdjListe {
POP[] poplist;
AdjListe (int popnum) {
poplist = new POP[popnum];
for (int i = 0; i < poplist.length; i++) poplist[i] = new POP();
}
void AddEdge (int from, int to, int way) {
poplist[from].addEdge(to, way);
poplist[to].addEdge(from, way);
}
void ShortestPaths (int start) {
int ways[] = new int[poplist.length];
for (int i = 0; i < poplist.length; i++) ways[i] = 0;
ways[start] = -1;
poplist[start].waycalc(ways, poplist, -1, start);
for (int i = 0; i < poplist.length; i++) {
if (ways[i] > 0) System.out.println("to " + i + " we need " + ways[i]);
else if (ways[i] == -1) System.out.println("we started at " + i);
else System.out.println("I'm very sad about " + i + "not being reachable :/");
}
}
public static void main (String args[]) {
AdjListe stinklist = new AdjListe(15);
stinklist.AddEdge(0,1,18);
stinklist.AddEdge(0,3,12);
stinklist.AddEdge(0,4,20);
stinklist.AddEdge(0,14,15);
stinklist.AddEdge(1,0,18);
stinklist.AddEdge(1,2,15);
stinklist.AddEdge(2,1,15);
stinklist.AddEdge(2,3,15);
stinklist.AddEdge(3,0,12);
stinklist.AddEdge(3,2,15);
stinklist.AddEdge(3,5,20);
stinklist.AddEdge(4,0,20);
stinklist.AddEdge(4,5,20);
stinklist.AddEdge(4,6,18);
stinklist.AddEdge(4,13,25);
stinklist.AddEdge(5,3,20);
stinklist.AddEdge(5,4,20);
stinklist.AddEdge(5,7,14);
stinklist.AddEdge(6,4,18);
stinklist.AddEdge(6,7,15);
stinklist.AddEdge(6,9,10);
stinklist.AddEdge(7,5,14);
stinklist.AddEdge(7,6,15);
stinklist.AddEdge(7,8,20);
stinklist.AddEdge(8,7,20);
stinklist.AddEdge(8,9,15);
stinklist.AddEdge(8,11,60);
stinklist.AddEdge(9,6,10);
stinklist.AddEdge(9,8,15);
stinklist.AddEdge(9,10,35);
stinklist.AddEdge(10,9,35);
stinklist.AddEdge(10,12,10);
stinklist.AddEdge(11,8,60);
stinklist.AddEdge(11,12,70);
stinklist.AddEdge(12,10,10);
stinklist.AddEdge(12,11,70);
stinklist.AddEdge(12,13,50);
stinklist.AddEdge(13,4,25);
stinklist.AddEdge(13,12,50);
stinklist.AddEdge(13,14,15);
stinklist.AddEdge(14,0,15);
stinklist.AddEdge(14,13,15);
/* Hier nun der Aufruf von shortest paths, welches laut aufgabenstellung
alle Wege von einem best. Punkt aus berechnet und anzeigt. */
stinklist.ShortestPaths(2);
}
}
Ich hab in den waycalcs noch nette printlns, die einem zeigen, wie das ding laeuft. kann man ja mal die kommentierung entfernen.
sieht man schoen, wie er fuer einige punkte immer kuerzere wege findet.
einen plan der wege hab ich leider nur in dem buch und keinen scanner (abgesehen davon, dass es nicht mein buch ist).
naja egal. falls das hier IRGENDWEN interessiert, kann er sich ja melden. ich erzaehl dann gern auch mehr dazu…
cu
Ford Prefect
dieses board laesst mich den post nicht mehr editieren ABBC fehler na danke! auch wenn ich special syntax ausmache (sehr sinnvoll!!)… also die (i)* waren mal /*
hmm, also ich konnte das grade problemlos editieren. irgendwas hast du da angestellt 
hab die special syntax auch gleich mal ausgemacht. das führt manchmal zu problemen in code-blöcken, wo ja bekanntlich keine bbcode-übersetzung stattfindet (auch sehr sinnvoll…)
Also gut, ich sehe du hast dich in Java ganz gut eingelebt…
(@all: ich bin der, der auch mit Scheme C programmieren kann…)
Nur muss ich leider sagen, dass dieses Programm mir leider nicht wesentlich zum Verständnis des Shortest Path Problems geholfen hat. Ich werd mir jetzt zuerst mal das vom Str… im anderen Forum drüben anschauen. Da ist alles schön in einer Funktion drin… kapier ich vielleicht schneller.
wenn du willst, kann ich auch mal eine kurze erläuterung geben. nachdem das mal wieder rekursiv ist und die rekursion über 2 Funktionen verteilt, stellt sich der Durchblick vielleicht nicht ganz so schnell ein.
Aber EIGENTLICH ist es ganz einfach 
ich will nur hier nicht das halbe board zuquatschen, ohne dass es einer liest…
geb mal eine kurze erlaeuterung!
habe das gerade auch selber gemacht und verstehe bei deinem auch nicht, was du da eigentlich so genau machen willst. thx!
Hi
Also gut, schauen wir es uns einfach nochmal an.
Die Funktion ShortestPaths leitet das Ganze ja ein:
ways ist ein Array, der für jeden Wegpunkt den bisher gefundenen kürzesten Weg vom Startpunkt aus speichert. ways[startpunkt] setze ich auf -1, damit geklärt ist, dass
a) überhaupt schon ein weg feststet (!= 0)
b) man garantiert keinen kürzeren weg mehr dahin findet
So, nun gehts weiter:
Vom Startpunkt aus leiten wir die Suche nach allen Wegen ein, die es von da aus gibt.
Schauen wir uns die zugehörige Funktion eines Wegpunktes mal an:
void waycalc (int[] ways, POP[] pops, int tillnow, int iself)
ways muss natürlich überreicht werden, genauso wie pops, welches notwendig ist, damit funktionen von den anderen wegpunktobjekten ausgeführt werden können. tillnow beschreibt, wie weit er schon vom Startpunkt aus gebraucht hat (Wegkosten). iself ist immer die nummer des Wegpunktes, an dem man sich gerade aufhält.
Wenn waycalc zum ersten mal aufgerufen wird (tillnow = -1) soll es nichts in ways speichern sondern nur die rekursion beginnen.
andernfalls ist zu überprüfen:
a) wurde noch kein Weg zu diesem Punkt gefunden?
b) wenn doch, ist dieser Weg länger als der aktuelle (tillnow!)
in diesem fall sind die aktuellen, geringeren wegkosten abzuspeichern UND die rekursion für die eigenen wege fortzusetzen.
ist dies NICHT der fall, so macht natürlich auch eine fortsetzung keinen sinn, da alle erreichbaren punkte schon einmal schneller erreicht wurden. die rekursion ist für diesen weg am ende.
schauen wir uns noch shcnell die funktion für ein listenelement eines wegpunktes an:
void waycalc (int[] ways, POP[] pops, int tillnow, int iself)
was übergeben wird, ist identisch.
nun brauchen wir pops, denn wir wollen einen zweig der rekursion starten, welcher eben beim wegpunkt beginnt, der durch den von uns gespeicherten weg erreicht wird. natürlich muss diesem das aktuelle tillnow + die kosten eben jenes weges mitgegeben werden.
nachdem wir diesen job erfüllt haben, müssen wir natürlich auch das nächste listenelement, falls vorhanden, anstoßen. hier bleibt tillnow natürlich gleich, denn es gehört ja immer noch zum gleichen punkt.
und am ende dieser lustigen rekursiererei wurden dann tatsächlich alle wege abgelaufen, die auch berücksichtigt werden müssen. aber eben keine schleifen, denn die werden verhindert.
noch eine kleine überlegung dazu: da nicht mitgeliefert wird, von welchem punkt ausm an den aktuellen punkt erreicht hat, geht natürlich auch eine rekursion wieder den schritt zurück. dort wird gestoppt, denn man war ja eben schon mal da und das logischerweise mit geringeren Kosten. Das könnte man verhindern, aber ich habe mir gedacht, den letzten wegpunkt noch mitzuliefern und an jedem listenelement zu vergleichen ist im endeffekt aufwendiger.
die methodik ist sehr auf die aufgabenstellung zugeschnitten. sie verliert ihre effizienz, wenn man nur den weg zu einem bestimmten punkt braucht, fürchte ich. also vielleicht könnte man da noch sparen, weiss ich nicht. bei einer speicherung der wege in einem array kann man sich jedenfalls was sparen. ist aber glückssache, wieviel.
cu
Ford Prefect