Guten Tag,
ich stehe vor einem Problem, weil mein Dijkstra-Algorithmus nicht funktioniert.
Ich bin den Code bereits mehrere male durchgegangen und finde einfach nicht die Lösung.
Vielleicht kann mir jemand von euch helfen.
ich stehe vor einem Problem, weil mein Dijkstra-Algorithmus nicht funktioniert.
Ich bin den Code bereits mehrere male durchgegangen und finde einfach nicht die Lösung.
Vielleicht kann mir jemand von euch helfen.
Java:
import java.util.*;
public class MyGraph extends VisualGraph
{
public MyGraph() {
super("Most Important Locations in Charlemagne");
}
/**
* Constructor for objects of class MyGraph
*/
public MyGraph(String title)
{
super(title);
}
public void tiefensuche(GraphNode pNode) {
resetMarks();
Stack myStack = new Stack(); //Erzeuge Stack
myStack.push(pNode); //pNode auf Stack
while(!myStack.isEmpty()) { //Solange Stack nicht leer...
//Rufe oberste Node vom Stack auf und entferne Node von diesem
GraphNode cNode = (GraphNode) myStack.top();
myStack.pop();
if(!cNode.isMarked()) { //Wenn Node nicht markiert
System.out.println(cNode.getName()); //Gebe Node aus
mark(cNode); //Markiere Node
//Füge alle Nachbarn dem Stack hinzu
List cList = cNode.getNeighbours_();
cList.toFirst();
while(cList.hasAccess()) {
GraphNode ccNode = (GraphNode)cList.getObject();
myStack.push(ccNode);
cList.next();
}
}
}
//ENDE
System.out.println("ENDE");
}
public void breitensuche(GraphNode pNode) {
resetMarks();
Queue myQueue = new Queue(); //Erzeuge Queue
myQueue.enqueue(pNode); //pNode in Queue
while(!myQueue.isEmpty()) { //Solange Queue nicht leer...
//Rufe erste Node von Queue auf und entferne Node aus dieser
GraphNode cNode = (GraphNode) myQueue.front();
myQueue.dequeue();
if(!cNode.isMarked()) { //Wenn Node nicht markiert
System.out.println(cNode.getName()); //Gebe Node aus
mark(cNode); //Markiere Node
//Füge alle Nachbarn der Queue hinzu
List cList = cNode.getNeighbours_();
cList.toFirst();
while(cList.hasAccess()) {
GraphNode ccNode = (GraphNode)cList.getObject();
myQueue.enqueue(ccNode);
cList.next();
}
}
}
//ENDE
System.out.println("ENDE");
}
public DijkstraNode sucheMinimum(){
List pList = getNodes();
double zahl = Double.MAX_VALUE;
DijkstraNode minimumNode;
minimumNode = null;
pList.toFirst();
while(pList.hasAccess()){
minimumNode = (DijkstraNode) pList.getObject();
zahl = minimumNode.getDistance();
if(zahl > ((DijkstraNode) pList.getObject()).getDistance()){
zahl = ((DijkstraNode) pList.getObject()).getDistance();
minimumNode = (DijkstraNode) pList.getObject();
}
pList.next();
}
return minimumNode;
}
public List kuerzesterWeg(DijkstraNode start, DijkstraNode end) {
start.setDistance(0.0);
DijkstraNode nextNode = null;
while(!allNodesMarked()){
nextNode = sucheMinimum();
nextNode.mark();
List nachbar = getNeighbours(nextNode);
nachbar.toFirst();
while(nachbar.hasAccess()){
if(!((GraphNode) nachbar.getObject()).isMarked()){
DijkstraNode distanzNode = (DijkstraNode) nachbar.getObject();
double distanz = nextNode.getDistance() + getEdgeWeight(distanzNode, nextNode);
if(distanzNode.getDistance() > distanz){
distanzNode.setDistance(distanz);
distanzNode.setParent(nextNode);
}
nachbar.next();
System.out.println(distanzNode.getParent());
}
}
}
System.out.println("Debug: Kürzester Weg von "+start.getName()+" nach "+end.getName());
return null;
}
[/Java]