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