Ich hab ein Problem mit der Implementation der PriorityQueue im Dijkstra Algorithmus. Da ich kaum mit Java gearbeitet habe funktioniert die Idee ganz gut aber sicher sind ein paar Syntax Fehler drin weswegen ich Fehler bekomme.
Fehlerausgabe: "Syntax error on token "double", invalid ArgumentList" z:18
Der Double Wert in der PriorityQueue ist der Wert den der jeweilige Knoten gerade besitzt und soll der Wert sein an dem die Queue die Knoten sortiert und mir den kleinsten ausgibt, der String ist der Knoten und soll zum Vergleich in der For Schleife dienen.
Der Algorithmus läuft so richtig nur mit der implementation der Queue hab ich Probleme. Ich hoffe das einer meinen Fehler findet.
Java:
import java.util.*;
public class Dijkstra extends WeightedGraph
{
final double INFINITE = Double.MAX_VALUE;
public Dijkstra()
{
super(true);
}
public HashMap<String, Double> dijkstra(String start)
{
HashMap<String, Double> distance = new HashMap<String, Double>();
PriorityQueue<String> Q = new PriorityQueue<String>(double, String); //Erstellt die Queue Q
//Distanzen aller Knoten auf Unendlich setzen
for(GraphNode nodes : getNodes()){
distance.put(nodes.getLabel(),INFINITE);
Q.insert(INFINITE, nodes.getLabel()); //alle Knoten mit Unendlich in Q einfügen
}
distance.put(start, 0.0); //Startwert bekommt Entfernung 0
Q.remove(INFINITE, start); //Den Start Knoten wieder entfernen
Q.Add(0.0, start); //und mit der Entfernung von 0.0 einfügen
while (!Q.isEmpty()) // Solange etwas in der Queue ist
{
String min = Q.extractObj(); // wird der kleinste Knoten entfernt
for (GraphNode n : getNodes()) // Für jeden Knoten
{
if (min == n) // Wenn dieser Knoten = Q dann
for (Edge e : n.getEdges())// Für jede Kante
{
if (distance.get(n.getLabel()) + e.getWeight() < distance.get(e.getDestNode().getLabel())) {
//distance + Gewicht < Zielknoten
Q.remove(distance.get(e.getDestNode().getLabel()),e.getDestNode().getLabel()); //Wird der zielknoten aus Q entfernt
Q.add(distance.get(n.getLabel()) + e.getWeight(), e.getDestNode().getLabel()); //und mit den neuen Werten wieder eingefügt
distance.put(e.getDestNode().getLabel(), distance.get(n.getLabel()) + e.getWeight());
//distance in Zielknoten schreiben
}
}
}
}
return distance; //Ergebnis zurückliefern
}
public static void main(String[] args)
{
Dijkstra Dij = new Dijkstra();
Dij.addNode("0");
Dij.addNode("1");
Dij.addNode("2");
Dij.addNode("3");
Dij.addNode("4");
Dij.addEdge("0", "1", 6);
Dij.addEdge("0", "3", 7);
Dij.addEdge("1", "3", 8);
Dij.addEdge("1", "4", -4);
Dij.addEdge("1", "2", 5);
Dij.addEdge("2", "1", -2);
Dij.addEdge("3", "2", -3);
Dij.addEdge("3", "4", 9);
Dij.addEdge("4", "2", 7);
Dij.addEdge("0", "1", 6);
Dij.addEdge("4", "0", 2);
System.out.println(Dij.dijkstra("0"));
}
}
Fehlerausgabe: "Syntax error on token "double", invalid ArgumentList" z:18
Der Double Wert in der PriorityQueue ist der Wert den der jeweilige Knoten gerade besitzt und soll der Wert sein an dem die Queue die Knoten sortiert und mir den kleinsten ausgibt, der String ist der Knoten und soll zum Vergleich in der For Schleife dienen.
Der Algorithmus läuft so richtig nur mit der implementation der Queue hab ich Probleme. Ich hoffe das einer meinen Fehler findet.