Denkanstoss beim DijkstraAlgorithmus

[Hassbrut]

Hi, ich muss mit dem Dijkstra-Algorithmus arbeiten. Es handelt sich hierbei um einen Algorithmus, der die kürzeste Strecke einer Route bestimmt. Siehe auch: http://n.ethz.ch/student/stammt/doc/Algorithmen/Dijkstra.html

Ich habmich damit beschäftig, verstehe ihn auch und versuche ihn gerade in mein Programm einzubauen.

Hab mir hierfür den Methodenaufbau überlegt:

DijkstraSuche(Startnode, Endnode)
{
Ereignisliste.add(Startnode)

do
{
tempNode = erstes Element der Ereignisliste setzen

********************************************************

getconnectedNode(erste Node in Ereignisliste) //gibt den Vector "connected" mit allen verbundenen Nodes zurück

********************************************************

"connected" mit vector "bereits_besucht" vergleichen //"bereits_besucht" ist anfangs leer
und gleiche Einträge aus "connected" löschen

********************************************************

erstes Element aus "Ereignisliste" in "bereits_
besucht" schreiben und aus ersterer löschen

********************************************************

Element aus "connected" in die Ereignis-
liste anfügen (mit Datentyp DijkstraNode):

prüfen:

If (Element aus connected in Ereignisliste vorhanden)
& (connected.Element.Zeit < Ereignisliste.Element.Zeit)
{
überschreibe Element
Setze VorgängerNode = tempNode
}

If (Element aus connected in Ereignisliste vorhanden)
& (connected.Element.Zeit >= Ereignisliste.Element.Zeit)
{
nichts
}

If (Element aus connected nicht in Ereignisliste vorhanden)
{
Schreibe connected.Element in Ereignisliste
Setze VorgängerNode = tempNode
}

********************************************************

}
while (Ereignisliste != leer);
}

Soweit so gut, hab alle Methoden, die ich dafür brauche geschrieben, als da wären:

public int getDistance(Node node1, Node node2)

public Vector VectorVergleich(Vector v_vergleichen, Vector v_zuvergleichen)

public boolean TestVector(Vector vector,Node node) 

public Vector getConnectedNode(Node node)

Jetzt mein Problem:

Ich arbeite ja mit dem Datentyp Node. Ist einfach nen Datentyp, der einen Punkt auf einer Karte darstellt.
Das Problem ist nur, dass der Dijkstra-Algorithmus mehr als diesen Datentyp braucht.

Wer sich damit auskennt oder den Link oben studiert wird feststellen, dass ich neben der aktuellen Node auch die VorgängerNode und den Abstand zwischen den Nodes (als Zeiteinheit) abspeichern muss.

Mein Ansatz war nun einen Datentyp DijkstraNode zu erschaffen, der 2 Typen Nodes und eine Integer-Zahl beinhaltet.
Sprich Node aktuelleNode = new Node() , VorgaengerNode und int Abstand;

Aber wie gehe ich damit um? Ich komm keinen Schritt weiter bei der Handhabung dieses neuen Datentyps.


Sofern irgendwer versteht, was ich hier zusammenposte , wäre ich super dankbar, wenn er mir da helfen könnte.

 

[Manderby]

Hallo,
bin der Schreiber des oben angegebenen Links, deshalb meld ich mich hier mal. Bin zwar kein Java-Experte, aber mein schlaues Buch zuhause erlaubt mir, dir hier einen Vorschlag zu machen.

Bei der Zeile

tempNode = erstes Element der Ereignisliste setzen

weiss ich nicht genau, ob ich das richtig verstanden habe: Meinst du damit einfach irgendein Element, dass nun zufälligerweise an erster Stelle steht, oder das FRÜHESTE Element?

Falls das erste zutrifft, heisst das, dass du keine Priority-Queue benutzt. Daher könnte es sein, dass ein Knoten in "bereits_besucht" von einem anderen Knoten aus schneller besucht werden kann, dies jedoch nicht passiert, da dieser Knoten ja schon in "bereits_besucht" enthalten ist. Dafür gibt es zwei Lösungen:
1. Du implementierst das Ganze mit einer Priority-Queue, nehme immer nur den frühesten Knoten aus der Ereignisliste. Ich empfehle einen Heap. Sodann hast du, sobald du bei einem Knoten ankommst, automatisch den schnellsten Weg für diesen Knoten gefunden, denn es gibt keine weitere Möglichkeit mehr, mit noch weniger Schritten zu diesem Knoten zu gelangen.
2. Du streichst das Array "bereits_besucht" vollständig. Dies bewirkt, dass die Laufzeit des Algorithmus explodieren könnte (muss aber nicht).

Und hier der Vorschlag:

class DijkstraNode extends Node {

  public DijkstraNode vorg;          //Zeiger auf den Vorgängerknoten
  public int dist;                   //Der Abstand

  //Konstruktor:
  DijkstraNode(int xvalue,int y){
    //Setze die Werte für Node (keine Ahnung, was diese Klasse
    //für Werte besitzt, ich nehme mal an x und y und beide protected)
    x=xvalue;
    y=value;
  }

  SetNewValues(int distanz, DijkstraNode vorgaenger){
    dist=distanz;
    vorg=vorgaenger;
  }
 
}

Die GetValues kannst du selbst programmieren.

Wie geht man damit um?

Anstelle dass du deine Werte in Nodes eingibst (irgendwo müssen die Werte ja eingetragen werden), gibst du sie in DijkstraNodes ein. Bsp (Bitte nicht böse sein, wenn die Syntax nicht stimmt ):

DikstraNode[] nodes=new DikstraNode[3];
nodes[1]=DikstraNode(25,44);
nodes[2]=DikstraNode(43,62);
nodes[3]=DikstraNode(76,93);

Sobald du bei einem der Punkte

If (Element aus connected in Ereignisliste vorhanden) 
If (Element aus connected nicht in Ereignisliste vorhanden)

ankommst, berechnest du die Distanz und trägst die neuen Werte ein:

SetNewValues(neuedistanz, neuervorgaenger);

Das ist alles.

Hoffe, das half etwas. Viel Spass mit Dijkstra, es gibt viele Abgründe!

 

[Hassbrut]

Puhh, das ist einiges auf einmal, jedenfalls für 06:30 Uhr...
Trotzdem big thx, werd mir das mal reinziehen, sobald ich wach bin.

TempNode ist schlicht die Variable, mit der einen Schritt vorher gearbeitet wurde, wenn nun

Element aus "connected" in die Ereignis-
liste anfügen

abgefragt wird, steht in der TempNode die Node, die die VorgängerNode ist.

Mit TempNode kann ich somit realisieren, dass er speichert, von welcher Node er zu einer anderen gekommen ist.
Beispiel: D2[A]
Dann ist D = die Node die als letztes in bereits_besucht geschrieben wurde, 2 die Zeit, [A] die Vorgänger/TempNode.
Als TempNode setze ich am anfang der do/while-Schleife immer das oberste Element der Ereignisliste, weil die ja permanent abgearbeitet wird.


PS.: Super Seite, hab den Dijkstra damit recht schnell verstanden. Respekt! :toll:

 

[meez]

Bau das Programm so, dass du die Wertigkeiten auch dynamisch verteilen kann, d.h. dass die Nodes (Router) ihre Tabellen weitergeben können...
Weil das wird der nächste Teil der Aufgabe sein.......
(btw. Dijkstra wird heute nicht mehr verwendet...Nur noch in Uebungen)

 

[bygones]

mhm - Dijkstra - durfte mich die letzten 4 monaten damit ausführlich beschäftigen.....
ehrlich gesagt: wenns geht - versuch eine library zu nehmen (z.b. http://www.jdsl.org).

Dijkstra ist nichts anderes als eine Variation einer Breitensuche bzw. Tiefensuche in einem Graph, nur dass die Knoten nicht in einem Stack oder Queue gehalten werde sondern in einer Priority Queue. Und eine gute Implementierung einer Priority Queue ist nicht an einem Tag zu machen....

daher mein Tipp: wenns geht: nimm eine lib (ist einfacher und meist auch besser)

(btw. Dijkstra wird heute nicht mehr verwendet...Nur noch in Uebungen)

Das stimmt nicht !! Ich benutze in noch
Aber meez hat recht - wenn du z.b. den weg in einem festen gitter suchst oder bzw eine Heuristik funktion nehmen kannst um zu schätzen wie weit dein knoten vom zielknoten entfernt ist, dann ist der A* Algorithmus besser

 

[Hassbrut]

Bau das Programm so, dass du die Wertigkeiten auch dynamisch verteilen kann, d.h. dass die Nodes (Router) ihre Tabellen weitergeben können...
Weil das wird der nächste Teil der Aufgabe sein.......

Hö? Welcher Teil für welche Aufgabe?

Blick jetzt garnet mehr durch, werd mir mal die Bibliothek ansehen, ansonsten nen Plan wie ich das mit dem Datentyp hinbekomme? Versteh's immernoch net so ganz.

 

[Manderby]

Bau das Programm so, dass du die Wertigkeiten auch dynamisch verteilen kann, d.h. dass die Nodes (Router) ihre Tabellen weitergeben können...
Weil das wird der nächste Teil der Aufgabe sein.......

Jetzt versteh ich glaubs, ihr wollt das OSPF-Protokoll (http://n.ethz.ch/student/stammt/doc/Netzwerk/OSPF.html) implementieren! Deswegen auch Router. Ich denke, damit ist gemeint: Führe den Dijkstra für jeden Knoten durch und speichere die jeweiligen Ergebnisse für sämtliche Knoten (oder vielleicht auch nur eine Teilmenge?) in dem Knoten selbst. Anders gesagt: Gehe durch alle Knoten durch, setze den Knoten als Startknoten und führe einen kompletten Dijkstra durch. Speichere das Ergebnis in einem Array der Form

DijkstraNode node;
int gesamtdistanz;

(Wobei du diese beiden Werte eventuell als eigene Klasse implementieren solltest)

Mit dynamisch ist gemeint:
Das was hier abläuft ist ein rein sequentieller Ablauf von einer Simulation mehrerer Knoten (zuerst Knoten 1, dann Knoten 2)

Um das ganze nun jedoch nicht-sequentiell zu machen (ich schätze, ihr geht jetzt dann auf das Thema Threads über) wurde nun der Dijkstra ausgewählt, da dieser gerade im OSPF-Protokoll (welches im Interent für die Router benötigt wird) verwendet wird (@meez: Dijkstra wird glaubs schon noch verwendet, den A*-Algorithmus kenn ich jedoch nicht, vielleicht kann dieser den Dijkstra ja ersetzen). Also wird der sequentielle Ablauf "Gehe durch alle Knoten durch..." ersetzt durch soetwas wie "frage mal deine Nachbarn, ob die vielleicht Informationen über den schnellsten Weg zu Knoten X haben".

Alles klar, oder?

 

[bygones]

Dijkstra wird glaubs schon noch verwendet, den A*-Algorithmus kenn ich jedoch nicht, vielleicht kann dieser den Dijkstra ja ersetzen

hat er eigentlich schon. A* arbeitet im gegensatz zum DIjkstra mit einer Heuristik Funktion die einem sagt wie weit geschätzt ein Knoten entfernt ist vom Zielknoten. Das hilft dem Algorithmus schneller seinen Weg zu finden.

Wenn aber für das gegebene Problem keine Heuristik Funktion gefunden werden kann, so ist und bleibt Dijkstra die einzige Wahl !

 

[Hassbrut]

Hey halt, ich progge mein Softwareprojekt zusammen für die Uni, wir müssen ein Streckennetz aufstellen und jetzt die kürzeste Route berechnen. Daher der Dijkstra.

Eigentlich wollte ich das so einfach wie möglich halten, doch jetzt versteh ich absolut garnichts mehr.

 

[Manderby]

Einfach nicht beachten, wir haben nur ein wenig gefachsimpelt (Mist, was ist schon wieder eine Heuristikfunktion? Ach ja, angepasste Wahrscheinlichkeit-Funktionen für gegebene Problemklasse ???:L ). @deathbyaclown: Komm jetzt nicht grad dazu, diese Thematik zu studieren, tönt aber spannend.

Also, die Sätze mit folgenden Wörtern einfach streichen, dann kommst du schon wieder draus: A*, Heuristik, Router, Thread, ospf. (Diejenigen mit Dijkstra würd ich lassen )
Mach den Dijkstra mal ganz normal, das ganze weitere Zeugs kommt dann in der nächsten Übung

 

[Hassbrut]

Okay ich setz mich jetzt ran und versuch nochmal die Variablen zu deixeln, wie gesagt das einzige Prob was ich noch mit Dijkstra hab.

 

[Hassbrut]

So hab's über den neuen Datentyp DijkstraNode(Node aktuelleNode, Node VorgaengerNode, int Abstand) geschafft!
Läuft alles super.
Der Quelltext sieht zwar aus, wie von 'nem Geisteskranken geschrieben, aber da kann man ja noch aufräumen.

Auf jeden big thx an alle, die sich hier beteiligt haben!