paths/de.jvstvshd.vyreka.path.routing.dijkstra/DijkstraAlgorithm

DijkstraAlgorithm

object DijkstraAlgorithm : RoutingAlgorithm(source)

Dijsktra's algorithm for finding the optimal path between two cells. Short description of the algorithm:

  1. Create a priority queue of paths.

  2. Add the start cell to the queue.

  3. While the last cell in the path is not the end cell:

    1. For each neighbor of the last cell:

      1. Fork the path to the neighbor.

      2. Add the forked path to the queue.

    2. Poll the queue to get the next path.

    3. Repeat until the last cell in the path is the end cell.

  4. Return the path. For more information, refer to Dijkstra's algorithm on Wikipedia.

Functions

Link copied to clipboard
open override fun findPath(start: Cell, end: Cell, travelCost: CellTravelCostSupplier): RoutingResult

Finds the optimal path between the start and end cell using the given travel cost supplier.

Link copied to clipboard
open override fun getAlgorithmName(): String

Gets the name of the algorithm.