dijskral implementierung

[kicy17]

hi

ich bin dabei für meinen kurs java-kurs einen dijkstral-algorithmus zu implementieren.
als ergebnis soll dabei ein gewichteter wurzelbaum (WeightedRootedTree) ausgegeben werden.

wir arbeiten in diesem kurs mit graphen und bäume.

wir haben einen GraphAlgorithms mit topologicalSort, computeBreadthSearchTree, computeDeepSearchTree und kruscal-methoden. ich weiß jetzt halt nicht, ob ich den dijkstral auch hier einfügen oder dafür eine eigene klasse schreiben soll. ich dachte ich kann mich da an dem kruskal-algorithmus orientieren:

der methoden-kopf vom kruskal sieht so aus:
public static <E, B> WeightedTree<E, B> kruscal(WeightedSimpleGraph<E, B> g, Comparator<Pair<E, E>> comp) {}

bloß statt des WeightedTree's dann den WeightedRootedTree benutzen... oder halt eine neue klasse dijkstral und dann noch eine vertex- und eine edge-klasse

kann mir da jemand weiterhelfen?

 

[Dekker]

Entschludigung wenn ich jetzt so blöd frage, aber meinst du Dijkstra? Ich hab noch nie was von Dijskral gehört und auch google spuckt diesbezüglich nur das Forum hier und irgendwelche chinesischen/japanischen Seite raus.

Und falls ja würde mich stark interessieren wie man sich das mit der Ausgabe vorzustellen hat. Verstehe nämlich den Sinn zwischen Dijkstra und der Ausgabe des Ergebnisses als Baum in welcher Form auch immer nicht. Klingt mir sehr zweifelhaft.

 

[faetzminator]

Dekker, warum meinst du, sind das gewichtete Graphen ? Er meint schon den Dijkstra...
@TO: Wie meinst du das genau? Ich versteh die Frage bzw. Aufgabe nicht wirklich.

 

[Firephoenix]

Hi,
wie will man denn von einem Kruskal auf einen Dijkstra kommen?
Dijkstra folgt immer dem kürzestem Weg bis er am Ziel angekommen ist, Kruskal wählt aus allen Kanten die kürzeste aus (Dijkstra berechnet dagegen gesamtweglängen über mehrere Kanten) und fügt die Kante in den Graph ein, so dass kein Zyklus entsteht.
Außerdem ist nicht klar, wie der Wurzel-Baum aussehen soll der da produziert wird.
Meiner Meinung nach macht es mehr sinn bei einem Dijkstra den kürzesten Weg zum Ziel auszugeben.
Oder soll die implementierung hier alle möglichen Wege die er geht als Baum ausgeben?
Gruß

 

[kicy17]

sorry, klar mein ich dijkstra

der algorithmus soll schon den kürzesten weg ausgeben.
die ausgabe soll einfach den startknoten, alle nachfolgende knoten auf dem kürzesten weg und dann den endknoten ausgeben.

ich zeig euch mal was wir bis jetzt in unserem framework schon implementiert haben:

import java.util.Collection;
import struct.relations.HomogeneRelation;
import java.util.Iterator;
import struct.SimpleSet;
import struct.relations.Pair;


public class DirectedGraph<E> {
  
protected final SimpleSet<E> vertices;   
protected final HomogeneRelation<E> relation;
  
public DirectedGraph() {
        
this.vertices = new SimpleSet<E>();       
this.relation = new HomogeneRelation<E>();
}

public DirectedGraph(SimpleSet<E> nodes, HomogeneRelation<E> edges) {
        
this.vertices = nodes;      
this.relation = edges;   
for (Pair<E, E> pair : edges) {          
if (!vertices.contains(pair.getFirst()) || !vertices.contains(pair.getSecond())) {            
throw new IllegalArgumentException("In der Relation sind Knoten enthalten, "
 + "die nicht in der Knotenmenge enthalten sind.");          
}      
}
}
  
public DirectedGraph(Collection<E> nodes, Collection<Pair<E, E>> edges) {
        
this.vertices = new SimpleSet<E>();
this.vertices.addAll(nodes);    
this.relation = new HomogeneRelation<E>();
        this.relation.addAll(edges);
}

public DirectedGraph(DirectedGraph<E> graph) {
     
vertices = new SimpleSet<E>();       
for (Iterator<E> i = graph.vertices(); i.hasNext(); 
addVertex(i.next()));
this.relation = new HomogeneRelation<E>();    
for (Iterator<Pair<E, E>> i = graph.edges(); i.hasNext(); addEdge(i.next()));
}

//hier stehen noch diverse methoden 

}

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;   
}
    
@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());    
}
   
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;  
}

}

dann hab ich noch eine klasse WeightedRootedTree implementiert mit extends RootedTree.
die klasse enthält zusaätzlich noch das attribut int weight.
und mit hilfe der klasse WeightedRootedTree soll ich den dijskra implementieren

könnt ihr damit was anfangen oder ist das alles nur noch mehr verwirrend?

 

[Landei]

Dijkstra's algorithm (Java) - LiteratePrograms

 

[Dekker]

Dekker, warum meinst du, sind das gewichtete Graphen ? Er meint schon den Dijkstra...
@TO: Wie meinst du das genau? Ich versteh die Frage bzw. Aufgabe nicht wirklich.

Aso ja klar. Dijkstra ist ja der einzigste Algorithmus mit gewichteten Kanten. Ich wollte eigentlich nur sichergehen. Kein Grund den Besserwisser raushängen lassen zu müssen....

@TE:

Was soll den der Baum darstellen. Ich glaube da harkts. Weil Dijkstra auf Bäumen ausführen ist Sinnfrei. Da diese Zyklenfrei sind kann man da doch nur die Pfade ausgeben. Etwas genauer wäre hier schon hilfreich, wie das gedacht ist.

 

[kicy17]

warum soll das den nicht bei einem baum gehen? es gibt ja verschiedene pfade und er soll mir einfach den kürzesten raussuchen.

dein link ist sowiet schon ziemlich zu gebrauchen, aber dann benutz ich die klasse WeightedRootedTree ja gar nicht...

 

[Dekker]

Wie gesagt, wofür ist der WeightedRootTree gedacht?

Natürlich kann man Dijkstra auf einen Baum ausführen, aber es gibt halt zu jedem Knoten genau 1 Pfad. Das ist ja das dolle an nem Baum. Ich verstehe nicht wie du drauf kommst das ein Baum unterschiedliche lange Pfade zu einem Knoten haben kann. Bäume sind per Definition zyklenfrei und bipartit.

Sollst du die Pfade zu jedem Knoten in diesem WeightedRootTree speichern? Oder stellt das den Ausgangsgraphen dar?

Edit:

Ok, hab mich selbst mal nen bissle schlau gemacht. Wenn ich richtige Rate wie deine Aufgabenstellung gemeint ist, dann sollst du den kürzesten Weg zu jedem Knoten von einem gegebenen Startknoten aus berechnen und danach die Knoten mit der Länge des kürzesten Weges zu eben jenem Knoten in den Baum einfügen. Das wäre das einzigste was auch nur irgendwie Sinn machen könnte. Du benutzt den Baum nur zur Darstellung des Ergebnisses, von daher macht es Sinn eine eigene Klasse für Dijkstra anzulegen. Man sollte immer Datenstrukturen und Logik trennen.

 

[kicy17]

ich dachte die klasse WRTree ist dafür da, dass man dann nicht noch extra eine klasse vertex und eine klasse edge implementieren muss, sondern die attribute und methoden da einbauen kann.

wir haben vorher andere algorithmen implementiert, wie breitensuche, kruskal, usw und die sind alle in der klasse GraphAlgorithm drinnen. wie ich schon mal gesagt habe, sieht das dann ungefähr so aus:

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

es ändert sich jeweils der ...Tree oder ...Graph im methodenkopf und dann halt die methoden an sich sind natürlich auch unterschiedlich

 

[Dekker]

Naja, im Normalfall beschreibt eine Vererbungshierarchie im Objektorientierten Sinn immer entweder eine Spezialisierung oder eben eine Verallgemeinerung, je nachdem, ob man in der Hierarchie beim Betrachten von unten oder von oben beginnt. Bei der Spezialisierung ist es normalerweise der Fall, das die Klasse, welche von der Oberklasse erbt zumindest einen Teil der Funktionalität der Oberklasse gleich hat, aber noch zusätzliche Constrains in eben jener Unterklasse hinzukommen.

Die interessante Fragen in diesem Falle wäre nun zuersteinmal zu klären, ob und wofür der WeightedTree bei Dijkstra genau verwendet werden sollte. Wenn ich mir z.b. deine Methode krucal ansehe, dann bekommt der Algorithmus zum einen einen WeightedSimpleGraph, zum anderen einen Comparator(welcher ja auch benötigt wird, damit du die Kanten vergleichen kannst). Als Rückgabewert hat der Algorithmus einen WeightedTree. Das macht auch sinn, denn Kruskal ist ein Algorithmus, welcher einen minimalen Spannbaum berechnet.
Bei Dijkstra müsstest du nun genauso einen einfachen gewichteten Graphen übergeben (also einen WeightedSimpleGraph), denn Dijkstra ist ja nunmal da um in einem gewichteten Graphen kürzeste Wege zu suchen. Was ich mir nun vorstellen kann ist, dass Dijkstra einen WeightedRootedTree zurückgeben soll. In diesen fügst du jeweils die Knoten mit der Länge des Pfades zu ihnen ein. Das kannst du z.b. immer am Ende jeder Runde machen, wenn ein neuer Knoten permanent als fertig markiert wurde (d.h. jede Runde einen).

Dein Methodenkopf sollte also meiner Meinung nach, wenn ich das richtig verstehe und rate (du möchtest ja scheinbar nicht mehr zur Aufgabe sagen ^^) wie folgt aussehen:

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

 

[kicy17]

also gut:

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 du noch ein Bild von der Baustelle.

mehr steht wirklich nicht in der Aufgabenstellung...

Also meinst du ich kann die Klassen Vertex und Edge weglassen und die Klassen WeightedRootedTree und GraphAlgorithm (in der dann die Dijskra-Algorithmus steht) benutzen?

 

[Landei]

Der Herr hieß Edsger Wybe Dijkstra, und hat genug für die Informatik geleistet, um wenigstens die richtige Schreibung seines Namens verdient zu haben.

 

[kicy17]

Das ich den Namen von dem Herrn Dijkstra ständig falsch schreibe hat aber nichts damit zu tun, das ich mit meiner Aufgabe nicht weiterkomme!

 

[Marco13]

Wenn du immer "Dijskra" in eine Suchmachine eintippst, und dann nur 1000 Ergebnisse bekommst (statt der 12.3 Millionen (!) bei "Dijkstra") könnte das schon sein.