# PriorityQueue im dijkstra Algorithmus implementieren



## tEhHoLLoW (2. Dez 2010)

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.


```
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.


----------



## SlaterB (2. Dez 2010)

Dijkstra und 77 deiner geposteten 78 Zeilen sind quasi egal, die Fehlermeldung sagt dir doch exakt was falsch ist,
hier dasselbe in einem kürzeren Programm:

```
public class Test
{
    public static void main(String[] args)
    {
        PriorityQueue<String> Q = new PriorityQueue<String>(double, String);
    }
}
```
diese Code-Zeile von dir ergibt schlicht keinen Sinn, nicht mehr und nicht weniger ist das Problem

verwende nur Code-Zeilen, die auch Sinn ergeben,
welchen Zweck verfolgst du damit, "double" nach der Klammer zu schreiben, was wäre wenn es nicht da steht?,
du musst dir doch etwas dabei gedacht haben, was ist das


edit:
> Der Double Wert in der PriorityQueue [..] soll der Wert sein

so funktioniert es nicht, Wünsche kann man nicht direkt reinbauen, PriorityQueue<String> ist allein eine Liste von Strings


----------



## tEhHoLLoW (2. Dez 2010)

Ich möchte ja Objekte in die Queue stecken die aus einem double und einen String wert bestehen, und der double Wert soll halt der Wert sein womit die Queue die Werte sortiert und mir den kleinsten wiedergibt.
Und ich habe mir halt gedacht das wenn ich eine Queue erstelle das ich in klammern schreibe welche Werte die Objekte annehmen die ich der Queue hinzufügen will. Und das ist ja (double,String). 
Wenn ich das weglasse gibt er mir bei jedem add oder remove Fehler an dass er die Objekte nicht hinzufügen kann.


----------



## SlaterB (2. Dez 2010)

die Fehler gibt es, weil die restlichen Aufrufe auch nicht so toll sind, in der ganzen API wirst du z.B. keine großgeschriebene Methode finden (Q.Add(0.0, start); ),
Variablen wie Q besser auch klein schreiben

so, um deinen Wunsch umzusetzen schlage ich vor, eine Klasse DistanceLabel anzulegen, mit Attributen double + String,
diese Klasse muss Comparable sein, in der compareTo-Methode wird nach double verglichen,

die Queue lautet dann

```
PriorityQueue<DistanceLabel> q = new PriorityQueue<DistanceLabel>()
```

nicht ganz leicht mit Comparable, aber eine gute Gelegenheit, damit anzufangen,
folgendes Buch-Kapitel hilft
Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 12 Datenstrukturen und Algorithmen


----------



## Andi_CH (2. Dez 2010)

EDIT: Ja, ich hätte update machen sollen, bevor ich mit tippen begonnen habe ;-) mea culpa


Erstens Variablennamen bitte klein schreiben
Zweiten Variablennamen bitte aussagekräftig wählen  - mehr als einen Buchstaben

-> z.B. PriorityQueue<String> prioQueue = new .........

Drittens Was für Konstruktoren bietet PriorityQueue denn so an?


```
public PriorityQueue() {}
    public PriorityQueue(int initialCapacity) {}
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {}
    public PriorityQueue(Collection<? extends E> c) {}
    public PriorityQueue(PriorityQueue<? extends E> c) {}
    public PriorityQueue(SortedSet<? extends E> c) {}
```

Das sind alle - es gibt keinen mit (double, String) bzw (double, E) als Profil...
also such dir den passenden aus.


----------

