Package shortestPath
Class ShortestPath<V>
java.lang.Object
shortestPath.ShortestPath<V>
- Type Parameters:
V
- Knotentyp.
Kürzeste Wege in Graphen mit A*- und Dijkstra-Verfahren.
- Since:
- 14.12.2023
-
Constructor Summary
ConstructorsConstructorDescriptionShortestPath(undirectedGraph.UndirectedGraph<V> g, Heuristic<V> h)
Konstruiert ein Objekt, das im Graph g kürzeste Wege nach dem A*-Verfahren berechnen kann. -
Method Summary
Modifier and TypeMethodDescriptiondouble
Liefert die Länge eines kürzesten Weges von Startknoten s nach Zielknoten g zurück.Liefert einen kürzesten Weg von Startknoten s nach Zielknoten g.boolean
searchShortestPath(V s, V g)
Sucht einen kürzesten Weg von Starknoten s zum Zielknoten g.void
setSimulator(sim.SYSimulation sim)
Diese Methode sollte nur verwendet werden, wenn kürzeste Wege in Scotland-Yard-Plan gesucht werden.
-
Constructor Details
-
ShortestPath
Konstruiert ein Objekt, das im Graph g kürzeste Wege nach dem A*-Verfahren berechnen kann. Die Heuristik h schätzt die Kosten zwischen zwei Knoten ab. Wird h = null gewählt, dann ist das Verfahren identisch mit dem Dijkstra-Verfahren.- Parameters:
g
- Gerichteter Graphh
- Heuristik. Falls h == null, werden kürzeste Wege nach dem Dijkstra-Verfahren gesucht.
-
-
Method Details
-
setSimulator
public void setSimulator(sim.SYSimulation sim)Diese Methode sollte nur verwendet werden, wenn kürzeste Wege in Scotland-Yard-Plan gesucht werden. Es ist dann ein Objekt für die Scotland-Yard-Simulation zu übergeben.Ein typische Aufruf für ein SYSimulation-Objekt sim sieht wie folgt aus:
if (sim != null) sim.visitStation((Integer) v, Color.blue);
- Parameters:
sim
- SYSimulation-Objekt.
-
searchShortestPath
Sucht einen kürzesten Weg von Starknoten s zum Zielknoten g.Falls die Simulation mit setSimulator(sim) aktiviert wurde, wird der Knoten, der als nächstes aus der Kandidatenliste besucht wird, animiert.
- Parameters:
s
- Startknoteng
- Zielknoten- Returns:
- true, falls es einen kürzesten Weg gibt.
-
getShortestPath
Liefert einen kürzesten Weg von Startknoten s nach Zielknoten g. Setzt eine erfolgreiche Suche von searchShortestPath(s,g) voraus.- Returns:
- kürzester Weg als Liste von Knoten.
- Throws:
IllegalArgumentException
- falls kein kürzester Weg berechnet wurde.
-
getDistance
public double getDistance()Liefert die Länge eines kürzesten Weges von Startknoten s nach Zielknoten g zurück. Setzt eine erfolgreiche Suche von searchShortestPath(s,g) voraus.- Returns:
- Länge eines kürzesten Weges.
- Throws:
IllegalArgumentException
- falls kein kürzester Weg berechnet wurde.
-