Dijkstra implementierung 2.0

kicy17

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

Java:
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;
    }


}

Java:
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

Top Contributor
(und wo ich hoffentlich Dijkstra immer richtig schreibe...)
...
Java:
...
public static <E, B> WeightedTree<E, B> kruscal(WeightedSimpleGraph<E, B> g, Comparator<Pair<E, E>> comp){}

Irgendwann klapp das mit dem Kruskal vielleicht auch noch :D

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

Mitglied
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?
 
M

Marcinek

Gast
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

Top Contributor
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

Mitglied
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...
 
M

Marcinek

Gast
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

Mitglied
Java:
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;
    }
}

Java:
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);

}

Java:
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?
 
M

Marcinek

Gast
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

Mitglied
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
 
M

Marcinek

Gast
Ok,

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

kicy17 teammate

Gast
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.
 
M

Marcinek

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

Schreibt mich an, falls ihr TS3 habt.
 
K

kicy17 teammate

Gast
Java:
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;
    }
 
K

kicy17 teammate

Gast
Beispiel für Breitensuche:

Java:
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;
    }
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Dijkstra Algorithmus Hilfe!! Java Basics - Anfänger-Themen 9
U Meinung zum Dijkstra Algorithmus Java Basics - Anfänger-Themen 6
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
S Dijkstra-Algoritmus Java Basics - Anfänger-Themen 7
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
S Dijkstra Algorithmus funktioniert nicht Java Basics - Anfänger-Themen 4
S GraphNode --- Dijkstra Algorithmus : NullPointerException Java Basics - Anfänger-Themen 1
Binary.Coder Tipp für Ein-/Ausgabe für Dijkstra Java Basics - Anfänger-Themen 6
B PriorityQueue im dijkstra Algorithmus implementieren Java Basics - Anfänger-Themen 4
T Dijkstra auf adjazenzmatrix Java Basics - Anfänger-Themen 7
ruutaiokwu JRE-/JDK-unabhängige PBKDF2WithHmacSHA512-Implementierung Java Basics - Anfänger-Themen 16
V Hilfe bei Implementierung einer boolean Methode Java Basics - Anfänger-Themen 6
K Fehler bei der Implementierung Java Basics - Anfänger-Themen 6
J Implementierung gcd();square() Java Basics - Anfänger-Themen 98
J Implementierung von Observer und Singleton-Pattern Java Basics - Anfänger-Themen 9
A Implementierung von String toString methode() Java Basics - Anfänger-Themen 4
G Projekt architektur (implementierung) Java Basics - Anfänger-Themen 3
M Implementierung einer getNextId Methode Java Basics - Anfänger-Themen 5
J Implementierung Listen-ADT Java Basics - Anfänger-Themen 131
J Implementierung eines Zustandsdiagramms Java Basics - Anfänger-Themen 19
I GenericQueue / Implementierung als Ringspeicher Java Basics - Anfänger-Themen 4
MiMa Log4j2 implementierung Java Basics - Anfänger-Themen 4
S Interface Interface und seine Implementierung Java Basics - Anfänger-Themen 5
G Array implementierung Java Basics - Anfänger-Themen 23
J ANTLR Installierung und Implementierung Java Basics - Anfänger-Themen 2
E Hilfe bei Implementierung von Methoden Java Basics - Anfänger-Themen 10
S SkipList Implementierung Java Basics - Anfänger-Themen 1
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
J Interface Probleme bei der Implementierung Java Basics - Anfänger-Themen 1
E hashCode implementierung Java Basics - Anfänger-Themen 9
S Implementierung der Klasse Konto und Nutzung bereits vorhandener Klassen Java Basics - Anfänger-Themen 7
H Implementierung eines Interfaces erweitern Java Basics - Anfänger-Themen 13
O Generics - Implementierung Java Basics - Anfänger-Themen 7
A Hilfestellung zur Implementierung des Gaußsches Eliminationsverfahren Java Basics - Anfänger-Themen 4
B OOP Implementierung eines Heaps Java Basics - Anfänger-Themen 13
K Bucketsort Implementierung Java Basics - Anfänger-Themen 0
K Mergesort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Klassen Klassendiagramm Implementierung? Java Basics - Anfänger-Themen 5
J Bucketsort Implementierung Java Basics - Anfänger-Themen 0
C Stack - listenbasierte Implementierung Java Basics - Anfänger-Themen 4
N Was bedeutet "Implementierung vor dem Client verbergen" bei Design Patterns? Java Basics - Anfänger-Themen 2
T Collections LinkedList<LinkedList<T>> - Implementierung Java Basics - Anfänger-Themen 10
F Implementierung von Interfaces -> Problem mit main Java Basics - Anfänger-Themen 12
D Resourcebundle implementierung Java Basics - Anfänger-Themen 2
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
Q Implementierung von Listenern Java Basics - Anfänger-Themen 4
B Klassen Hilfe bei Implementierung Java Basics - Anfänger-Themen 5
N Compiler-Fehler Comparable / compareTo implementierung Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Binärbaums Java Basics - Anfänger-Themen 3
I Erste Schritte Implementierung der API Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Adressbuches Java Basics - Anfänger-Themen 20
M falsche implementierung von currentTimeMillis() ? Java Basics - Anfänger-Themen 14
G Implementierung eines Kontos Java Basics - Anfänger-Themen 11
M Quicksort implementierung Java Basics - Anfänger-Themen 23
SexyPenny90 Implementierung einer doubly linked list Java Basics - Anfänger-Themen 5
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
U Doppelte Interfcae Implementierung Java Basics - Anfänger-Themen 10
K Kleiner Fehler bei Methoden Implementierung Java Basics - Anfänger-Themen 6
M Collections Problem bei Überschreibung von hashcode() und equals() bei Hashset-Implementierung Java Basics - Anfänger-Themen 5
S OOP Implementierung Komposition, Aggregation, Assoziation und Generalisierung Java Basics - Anfänger-Themen 2
C Klassenhirarchien zur Implementierung von Fahrzegen Java Basics - Anfänger-Themen 26
BinaryLogic Datentypen Statistik Interface - untersch. Implementierung Java Basics - Anfänger-Themen 5
E Performante Implementierung eines "Hintergrundprogramms" Java Basics - Anfänger-Themen 10
S Saubere Implementierung Java Basics - Anfänger-Themen 2
K dijskral implementierung Java Basics - Anfänger-Themen 14
U Probleme mit Server-Client implementierung Java Basics - Anfänger-Themen 5
K Game of Life Implementierung Java Basics - Anfänger-Themen 30
B OOP Problem bei Implementierung von Interface Java Basics - Anfänger-Themen 6
J HashSet Implementierung Java Basics - Anfänger-Themen 16
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
X Frage zur Implementierung von equals() Java Basics - Anfänger-Themen 2
B Effektive Implementierung für Darstellung großer Datenmengen in Jogl Java Basics - Anfänger-Themen 5
D Datentypen Implementierung eines Binärbaumes Java Basics - Anfänger-Themen 7
B Implementierung Java Basics - Anfänger-Themen 2
N Implementierung Tic tac toc Java Basics - Anfänger-Themen 25
O Stack Implementierung als verkettete Liste Java Basics - Anfänger-Themen 8
Y Implementierung einer Potenzturm Funktion Java Basics - Anfänger-Themen 4
S Implementierung gegen Interfaces / List, ArrayList, LinkedList Java Basics - Anfänger-Themen 11
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
U Implementierung Constructor Java Basics - Anfänger-Themen 7
T Problem mit Implementierung von einer HashMap aufgabe Java Basics - Anfänger-Themen 2
G Implementierung des Observer/Observable Patterns - Gut so? Java Basics - Anfänger-Themen 3
I Zugriff auf Implementierung verhindern Java Basics - Anfänger-Themen 8
D Implementierung nach MVC Java Basics - Anfänger-Themen 6
B Theoretische Frage zum Programmbau (nun zur Implementierung) Java Basics - Anfänger-Themen 8
H Implementierung von Interfaces Java Basics - Anfänger-Themen 4
G Implementierung von Bäumen Java Basics - Anfänger-Themen 2
N Probleme mit paint() bei Implementierung in ein Panel Java Basics - Anfänger-Themen 4
B Wie funktioniert die implementierung von c code in Java? Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Neue Themen


Oben