Package shortestPath

Class ShortestPath<V>

java.lang.Object
shortestPath.ShortestPath<V>
Type Parameters:
V - Knotentyp.
public class ShortestPath<V> extends Object
Kürzeste Wege in Graphen mit A*- und Dijkstra-Verfahren.
Since:
14.12.2023

  • Constructor Summary

    Constructors
    Constructor
    Description
    ShortestPath​(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 Type
    Method
    Description
    double
    getDistance()
    Liefert die Länge eines kürzesten Weges von Startknoten s nach Zielknoten g zurück.
    List<V>
    getShortestPath()
    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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • ShortestPath

      public ShortestPath​(undirectedGraph.UndirectedGraph<V> g, Heuristic<V> h)
      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 Graph
      h - 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

      public boolean searchShortestPath​(V s, V g)
      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 - Startknoten
      g - Zielknoten
      Returns:
      true, falls es einen kürzesten Weg gibt.

    • getShortestPath

      public List<V> 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.