public class Dijkstra
{
private List knoten = new List();
private List rand = new List();
private Graph mygraph;
boolean eingefuegt;
//länge??
public Dijkstra(Graph pgraph)
{
mygraph = pgraph;
}
public List starter(GraphNode pstart, GraphNode ziel)
{
DijkstraNode start = new DijkstraNode(pstart, 0.0, pstart);
if(pstart != ziel)
{
mygraph.resetMarks();
kuerzesterWeg(start, ziel);
}
//knoten auslesen
return wegauslesen(pstart, ziel);
}
private void kuerzesterWeg(DijkstraNode startKn, GraphNode zielKn)
{
while(!mygraph.allNodesMarked())
{
startKn.getvorgängerKn().mark(); // markiere Vorgängerknoten
knoten.append(startKn);
List nachbar = mygraph.getNeighbours(startKn.getknoten()); // Nachbarliste des Knotens
nachbar.toFirst();
while(nachbar.hasAccess())
{
if(!((GraphNode) nachbar.getObject()).isMarked()) // Nachbar unmarkiert?
{
double weight = startKn.getgewicht() + gewicht(startKn.getknoten(),(GraphNode) nachbar.getObject()); // Gesamtgewicht
DijkstraNode DN = new DijkstraNode(((GraphNode) nachbar.getObject()), weight, startKn.getknoten()) ; // neuer Dijkstranode
rand = sort_insert(rand,DN); // nach Gewicht sortiert eingefügt in den Rand
System.out.println("sortiert eingefügt: " + DN.getknoten().getName() + " mit dem Gewicht: " + weight);
((GraphNode) nachbar.getObject()).mark();
}
nachbar.next();
}
rand.toFirst();
if(rand.hasAccess())
{
DijkstraNode helfer = new DijkstraNode((DijkstraNode) rand.getObject()); // DijkstraNode mit dem kleinsten Gewicht aus dem Rand holen
rand.remove(); // und aus dem Rand löschen
System.out.println("---------- rekursiver Aufruf: " + helfer.getknoten().getName() + "-----------------");
kuerzesterWeg(helfer, zielKn); // rekursiver Aufruf
}
}
}
private List wegauslesen(GraphNode start, GraphNode ziel)
{
List weg = new List();
DijkstraNode dntemp = new DijkstraNode(ziel, 0.0, start); // ??
GraphNode gntemp = new GraphNode(""); // Knoten erstellt
knoten.toLast(); // letztes Element aus Knotenliste
while(knoten.hasAccess() || ziel == start) // Schleife, solange bis die Liste durch ist oder der Zielknoten=Startknoten ist
{
dntemp = (DijkstraNode) knoten.getObject(); // dntemp ist letztes Element aus der Knotenliste
gntemp = (GraphNode)dntemp.getknoten();
if(gntemp.getName().equals(ziel.getName()))
{
weg.toFirst();
weg.insert(gntemp);
ziel = dntemp.getvorgängerKn();
}
knoten.remove();
knoten.toLast();
}
return weg;
}
private double gewicht(GraphNode startKn, GraphNode zielKn)
{
if(startKn!=zielKn)
{
double kantengewicht = mygraph.getEdgeWeight(startKn,zielKn);
return kantengewicht;
}
else
{
return 0;
}
}
private List sort_insert(List prand, DijkstraNode pDN)
{
prand.toFirst(); // springe an den Anfang der Liste
eingefuegt = false;
if(prand.isEmpty()) // Falls die Liste leer ist
{
prand.append(pDN); System.out.println("1.objekt im rand");
eingefuegt = true;
}
else // falls die Liste nicht leer ist
{
while ((eingefuegt == false) && (prand.hasAccess()) )
{
DijkstraNode aktuellerDN = (DijkstraNode) prand.getObject();
if(pDN.getknoten().getName().equals(aktuellerDN.getknoten().getName()))
{
System.out.println("2 knoten gleich");
if(pDN.getgewicht() > aktuellerDN.getgewicht())
{
eingefuegt = true; // wenn der schon vorhandene DN ein kleineres Gewicht hat, brauch man nix mehr tun
System.out.println("vorhandener Knoten hat kleineres Gewicht");
}
else
{
prand.remove(); // andernfalls: vorhandenen DN löschen und später pDN sortiert einfügen
System.out.println("vorhandener Knoten gelöscht");
}
}
prand.next();
}
prand.toFirst();
while ((eingefuegt == false) && (prand.hasAccess()) ) //solange nicht eingefügt und nicht am Ende der Liste
{
DijkstraNode aktuellerDN = new DijkstraNode((DijkstraNode) prand.getObject());
if (pDN.getgewicht() < aktuellerDN.getgewicht())
//Falls das übergebene Gewicht kleiner als das Aktuelle (in der Liste) ist
{
prand.insert(pDN); //füge die neue DijkstraNode vor der aktuellen ein
eingefuegt = true; // schon eingefügt
System.out.println("neuer DN eingefügt");
}
else //falls das übergebene Gewicht größer als das aktuelle ist
{
prand.next(); //gehe eine Position weiter in der Liste
}
}
}
if(!eingefuegt) // Falls die Liste leer ist
{
prand.append(pDN);
eingefuegt = true;
}
System.out.println("Liste wird zurückgegeben mit den Elementen: ");
prand.toFirst();
while(prand.hasAccess())
{
System.out.println(((DijkstraNode) prand.getObject()).getknoten().getName() +", "+ ((DijkstraNode) prand.getObject()).getgewicht() +", "+ ((DijkstraNode) prand.getObject()).getvorgängerKn().getName());
prand.next();
}
return prand;
}
}
