# Dijkstra implementierung 2.0



## kicy17 (16. Jun 2011)

Hi, ich dachte ich erstelle besser ein neues Thema, damit alles etwas übersichtlicher ist 
(und wo ich hoffentlich Dijkstra immer richtig schreibe...)

noch mal die Aufgabe:

Implementieren Sie den Algorithmus von Dijskra. Als Ergebnis der Berechnung soll ein gewichteter wurzelbaum ausgegeben werden. Testen Sie Ihren Algorithmus anhand des Ergebnisses aus Aufgabenteil 3.3

Aufgabe 3.3: Um den Verkehr auf der Baustelle sinnvoll zu leiten, sollen die kürzesten Wege von der Zufahrt zur Baustelle (Knoten H1) zu allen anderen Knoten bestimmt werden. Bestimmen Sie mit dem Algorithmus von Dijkstra alle kürzesten wege und zeigen Sie den zugehörigen Wurzelbaum auf. Um nicht den Wurzelbaum für jeden Teilbaum ausgeben zu müssen, geben Sie den finalen Wurzelbaum sowie die Entwicklung der Kandidatenliste (Knoten mit gleicher Bewertung alphabetisch einsortiert) an.

Im Anhang findest man das Bild von der Baustelle.


```
public final class GraphAlgorithms {

public static <E> Abbildung<Integer, SimpleSet<E>> topologicalSort(DirectedGraph graph){}

public static <E> RootedTree<E> computeBreadthSearchTree(DirectedGraph<E> graph, E root){}

public static <E, B> WeightedTree<E, B> kruscal(WeightedSimpleGraph<E, B> g, Comparator<Pair<E, E>> comp){}

public static <E> WeightedRootedTree<E> dijkstra(WeightedSimpleGraph<E> graph, E root) {

        //Suchbaum, der am Ende zurueckgegeben wird.
        WeightedRootedTree<E> tree = new WeightedRootedTree<E>(root);
        //SimpleSet zum Buchfuehren, welcher Knoten noch nicht besucht wurde.
        SimpleSet<E> unVisitedNodes = new SimpleSet<E>(graph.getVertices());
        unVisitedNodes.remove(root);

        double minDistance = Double.POSITIVE_INFINITY;

        root.minDistance = 0.;
        PriorityQueue<E> candidates = new PriorityQueue<E>();
      	candidates.add(root);

        while (!candidates.isEmpty()) {
	    E k = candidates.poll();

            // Visit each edge exiting u
            for (E n : graph.getSuccessors(k)) {
                if (unVisitedNodes.contains(n)) {
                    unVisitedNodes.remove(n);
                    candidates.offer(n);
                    tree.addChild(n, k);
                }
            }
        }
        return tree;
    }


}
```


```
public class WeightedRootedTree<E> extends RootedTree<E> {

    public int weight;

    public WeightedRootedTree(E root, int weight) {
        super(root);
        super.addVertex(root);
        this.weight = weight;
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public E getRoot() {
        return root;
    }

    @Override
    public E getParent(E child) {
        return getPredecessors(child).iterator().next();
    }

    @Override
    public boolean isLeaf(E vertex) {
        return getPredecessors(vertex).isEmpty();
    }

    @Override
    public boolean isDescendant(E child, E ancestor) {
        if (containsVertex(child)) {
            if (ancestor.equals(root)) {
                return true;
            }
            E parent = getPredecessors(child).iterator().next();
            while (!parent.equals(root)) {
                if (parent.equals(ancestor)) {
                    return true;
                }
                parent = getPredecessors(parent).iterator().next();
            }
        }
        return false;
    }
    
    @Override
    public boolean addVertex(E vertex) {
        throw new UnsupportedOperationException("Adding a single vertex to a "
                + "tree can't garantee the tree definition. Use "
                + "<tt>addChild(E child, E parent)</tt> instead");
    }

    @Override
    public boolean addEdge(Pair<E, E> edge) {
        return addChild(edge.getSecond(), edge.getFirst());
    }

    @Override
    public boolean addChild(E child, E parent) {
        if (containsVertex(child)) {
            throw new IllegalArgumentException("a vertex in a tree can't"
                    + " have more then one parent");
        }
        super.addVertex(child);
        boolean add = super.addEdge(new Pair<E, E>(parent, child));
        if (!add) {
            super.removeVertex(child);
        }
        return add;
    }

    @Override
    public String toString() {
        String str = "Wurzel = " + this.getRoot() + ";\n";
        str += super.toString();
        return str;
    }  
}
```

Das sind meine zwei Klassen mit denen ich programmiere. Beim Dijkstra-Algorithmus komme ich jetzt aber nicht weiter und ich glaube, der ist so auch noch nicht ganz richtig


----------



## Marco13 (16. Jun 2011)

kicy17 hat gesagt.:


> (und wo ich hoffentlich Dijkstra immer richtig schreibe...)
> ...
> 
> ```
> ...



Irgendwann klapp das mit dem Kruskal vielleicht auch noch 

Im Moment ist das, soweit ich das sehe, der Cuthill-McKee oder so... Wo speicherst du denn überhaupt die distanzen für die einzelnen Knoten? Im Moment scheint nur "root" distanz 0 zu haben... aber alle anderen...?


----------



## kicy17 (17. Jun 2011)

Die anderen Knoten habe ich noch nicht implementiert. Ich weiß auch nicht wo ich das machen soll. Entweder im WeightedRootedTree oder im Dijkstra...

Mit Cuthill-McKe kann ich nichts anfangen. Was soll das denn sein?


----------



## Marcinek (17. Jun 2011)

Erst mal die Frage: Verstehst du das, was da schon steht?


----------



## kicy17 (17. Jun 2011)

Nicht wirklich, zumindest nicht alles...
Die anderen Algorithmen sind ja auch nicht von mir.


----------



## Marcinek (17. Jun 2011)

Ich glaube nicht, dass du das mit Hilfe eines Forums wirklich schaffen wirst.

Also MUSST das mit diesen Methoden machen, die du da versuchst du implementieren, oder ist das nur ein Versuch von dir?

Du hast hier ein Graphenmodell und etwas, was auf diesem Modell rechnet.

Das Model ist hier aber nicht vollständig implementiert. Das müsste man zuerst machen, damit man die Algos auch wirklich testen kann.

Ich würde vorschlagen, dass du das für diese zwecke selbst implementierst.

Dafür müsste man sich anschauen, was so ein Knoten alles leisten muss.


----------



## Marco13 (17. Jun 2011)

Der Graph scheint eigentlich schon alles zu bieten, was man braucht - und für den Dijkstra braucht man eigentlich nur "getSuccessors"...

Du musst auch keine weiteren Knoten implementieren ... aber da steht schon
root.minDistance = 0.;
(wobei ich mich frage, wie das geht, wenn der Typ nicht bekannt ist...). Die anderen Knoten brauchen am Anfang eben
node.minDistance = Float.POSITIVE_INFINITY;
und diese Werte müssen dann aktualisiert werden (und die Priority Queue auf Basis dieser Werte neu sortiert werden, was ein bißchen schwierig sein kann...)


----------



## kicy17 (18. Jun 2011)

Also das mit "root.minDistance = 0.;" geht nicht wirklich.
Da zeigt er mir einen Fehler an. 
Ich werde dann einfach noch bisschen probieren. Bis Montag hab ich noch Zeit...


----------



## Marcinek (18. Jun 2011)

Per Definition ist der Abstand von root meist 0, weil da möchtest du ja die Reise starten 

Aber der Wert ist auch egal, sollte aber nicht unendlich sein, weil dann der kürzeste Pfad min. Unendlich lang ist ;P

"rumprobieren" kannst du da garnix.

Ich  bin noch ein wenig im TS, kannst ja vorbeikommen. Schreib einfach eine PM.


----------



## kicy17 (19. Jun 2011)

```
package struct.graph;

import struct.relations.Pair;

public class RootedTree<E> extends DirectedGraph<E> {
     
private final E root;
    
public RootedTree(E root) {
        this.root = root;
        super.addVertex(root);
    }
   
public E getRoot() {
        return root;
    }
 
public E getParent(E child) {
        return getPredecessors(child).iterator().next();
    }

public boolean isLeaf(E vertex) {
        return getPredecessors(vertex).isEmpty();
    }

public boolean isDescendant(E child, E ancestor) {
        if (containsVertex(child)) {
            if (ancestor.equals(root)) {
                return true;
            }
            E parent = getPredecessors(child).iterator().next();
 
           while (!parent.equals(root)) {
                if (parent.equals(ancestor)) {
                    return true;
                }
                parent = getPredecessors(parent).iterator().next();
            }
        }
 
    return false;
}
    
public boolean addVertex(E vertex) {
        throw new UnsupportedOperationException("Adding a single vertex to a "
                + "tree can't garantee the tree definition. Use "
   
             + "<tt>addChild(E child, E parent)</tt> instead");
    } 

public boolean addEdge(Pair<E, E> edge) {
        return addChild(edge.getSecond(), edge.getFirst());
    }

public boolean addChild(E child, E parent) {
        if (containsVertex(child)) {
            throw new IllegalArgumentException("a vertex in a tree can't"
                    + " have more then one parent");
        }
       
 super.addVertex(child);
        boolean add = super.addEdge(new Pair<E, E>(parent, child));
        if (!add) {
            super.removeVertex(child);
        }
        return add;
    }

public String toString() {
        String str = "Wurzel = " + this.getRoot() + ";\n";
        str += super.toString();
        return str;
    }
}
```


```
package struct.graph.weighted;

import struct.relations.Abbildung;
import struct.relations.Pair;

public interface Weighted<E, B> {   

public void setWeight(Pair<E, E> edge, B bewertung);
    
public B getWeight(Pair<E, E> edge);
   
public Abbildung<Pair<E, E>, B> getWeights();

public boolean addEdge(Pair<E, E> edge, B bewertung);

}
```


```
package struct.graph.weighted;

import struct.graph.RootedTree;
import struct.relations.Abbildung;
import struct.relations.Pair;

public class WeightedRootedTree<E, B> extends RootedTree<E> implements Weighted<E, B> {

public Abbildung<Pair<E, E>, B> weights;

public WeightedRootedTree(E root, Abbildung<Pair<E, E>, B> weights ) {
        super(root);
        this.weights = new Abbildung<Pair<E, E>, B>();
    }

public void setWeight(Pair<E, E> edge, B bewertung) {
        this.weights.add(edge, bewertung);
    }
 
public B getWeight(Pair<E, E> edge) {
        return weights.get(edge);
    }
 
public Abbildung<Pair<E, E>, B> getWeights() {
        return weights;
    }
    
public boolean addEdge(Pair<E, E> edge, B bewertung) {
        this.setWeight(edge, bewertung);
        return this.addEdge(edge);
    }

}
```

so, ich habe meine grundlagen für den später folgenden dijkstra überarbeitet.
funktioniert das so besser und was fehlt denn noch?


----------



## Marcinek (19. Jun 2011)

Und noch mal die Frage: Verstehst du, was da steht?


----------



## kicy17 (19. Jun 2011)

joa, eigentlich schon


----------



## kicy17 (19. Jun 2011)

die klasse weightedrootedtree hab ich selbst geschrieben. die anderen beiden sind schon vorgegeben im framework


----------



## Marcinek (19. Jun 2011)

public Abbildung<Pair<E, E>, B> weights;

Hier haben wir eine Abbildung zweiter Kanten mit einem B, was wohl Bewertung seinsoll.

Angenommen ich habe eine Kante 

AB dann möchte ich davon die Bewertung haben, damit der algo prüfen kann, ob diese Strecke besser als eine schon vorhandene ist.

Dann mache ich was?

public B getWeight(Pair<E, E> edge);

Und übergebe ein Paar von Kanten? 

Glaube hier ist noch was durcheinander.

Maybe postest du die komplette Aufgabenbeschreibung? -Was ist durch wen Gott gegeben und was hast du dazu überlegt?


----------



## kicy17 (19. Jun 2011)

die aufgabenstellung steht ja ganz oben. das framework mit dem wir arbeiten hat alle klassen die wir brauchen.
unsere aufgabe besteht darin, das wir ein klasse weightedrootedtree erstellen und mit deren hilfe den dijkstra implementieren


----------



## Marcinek (19. Jun 2011)

Ok,

dann würde ich anfangen diesen zu implementieren. Meiner Meinung nach kommst du dan an das von mir beschriebene Problem.


----------



## kicy17 teammate (19. Jun 2011)

public static <E, B> WeightedRootedTree<E,B> dijkstra(WeightedSimpleGraph<E,B> graph, E root, B weights) {

        //Suchbaum, der am Ende zurueckgegeben wird.
        WeightedRootedTree<E,B> tree = new WeightedRootedTree<E,B>(root);



so haben wir jetzt angefangen den dijkstra zu proggen. jetzt kommt aber ne fehlermeldung, dass hinter dem new das "weightedrootedtree" nicht findet.


----------



## Marcinek (19. Jun 2011)

Falls ihr solche Fragen habt, dann kann man das nicht über ein Forum klären 

Schreibt mich an, falls ihr TS3 habt.


----------



## kicy17 teammate (19. Jun 2011)

```
public static <E, B> WeightedRootedTree<E,B> dijkstra(WeightedSimpleGraph<E,B> graph, E root, B weights) {

        //Suchbaum, der am Ende zurueckgegeben wird.
        WeightedRootedTree<E,B> tree = new WeightedRootedTree<E,B>(root);
        //SimpleSet zum Buchfuehren, welcher Knoten noch nicht besucht wurde.
        SimpleSet<E> unVisitedNodes = new SimpleSet<E>(graph.getVertices());
        unVisitedNodes.remove(root);
        
        PriorityQueue<E> candidates = new PriorityQueue<E>();
      	candidates.add(root);

        while (!candidates.isEmpty()) {
	    E k = candidates.poll();

            // Visit each edge exiting u
            for (E n : graph.getSuccessors(k)) {
                if (unVisitedNodes.contains(n)) {
                    unVisitedNodes.remove(n);
                    candidates.offer(n);
                    tree.addChild(n, k);
                }
            }
        }
        return tree;
    }
```


----------



## kicy17 teammate (19. Jun 2011)

Beispiel für Breitensuche:


```
public static <E> RootedTree<E> computeBreadthSearchTree(DirectedGraph<E> graph, E root) {
        //Suchbaum, der am Ende zurueckgegeben wird.
        RootedTree<E> tree = new RootedTree<E>(root);
        //SimpleSet zum Buchfuehren, welcher Knoten noch nicht besucht wurde.
        SimpleSet<E> unVisitedNodes = new SimpleSet<E>(graph.getVertices());
        unVisitedNodes.remove(root);

        Queue<E> candidates = new ConcurrentLinkedQueue<E>();
        candidates.offer(root);

        while (!candidates.isEmpty()) {
            E k = candidates.poll();
            for (E n : graph.getSuccessors(k)) {
                if (unVisitedNodes.contains(n)) {
                    unVisitedNodes.remove(n);
                    candidates.offer(n);
                    tree.addChild(n, k);
                }
            }
        }
        return tree;
    }
```


----------

