Java:
public class Dijkstra<V extends EuclidianVertex, E extends EuclidianEdge<V>> {
//Algorithmus findet den kürzesten Pfad zwischen zwei Knoten
public List<E> perform(Graph<V, E> graph, V start, V end) {
HashMap<V,Double> dist = new HashMap<V,Double>();
dist.put(start,); //to do
HashMap<V,V> pred = new HashMap<V, V>();
pred.put(end, end); //to do
HashSet<V> va = (HashSet)graph.vertices();
for(V u : graph.vertices()){
dist.put(u, Double.POSITIVE_INFINITY);
pred.put(u, null);
}
//Hier beginnt der eigentliche Algorithmus
while(va.size()>0){
u = dist.put(u, Double.MIN_VALUE);
va.remove(va); //to do
if(u == end)
break;
for(V v : graph.neighbors(end)){ //to do
if((dist.put(u, Double.POSITIVE_INFINITY) + start.distance(v))
< dist.put(v, Double.POSITIVE_INFINITY)){
dist = dist + d;
pred = u;
}
}
}
LinkedList<E> p;
E knoten = (E)graph.edges();
while(pred.put(u,Double.POSITIVE_INFINITY ) != null){
p = p.add(, knoten); //to do
u = pred.put(u, Double.POSITIVE_INFINITY);
}
return p;
}
}
Zuletzt bearbeitet von einem Moderator: