Dijkstra<E> class
final
Pathfinding
Pathfinding algorithm that finds the best path in a weighted graph.
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks, networks of pipes, or tiles on a grid. It starts at a source node and explores branches of the graph along all possible paths as far as necessary, backtracking when it fails to find the goal, or the cost of the path exceeds a previously found path with a lower cost.
Dijkstra's algorithm is a generalization of the breadthFirstSearch
algorithm. It is guaranteed to find the shortest path from the source node,
but it has a potentially high runtime complexity (O((V + E) log V) where
V is the number of vertices and E is the number of edges), as in the
worst case it may visit every edge in the graph.
A default singleton instance of this class is dijkstra.
- Mixed in types
Constructors
- Dijkstra()
-
Creates a new Dijkstra's algorithm.
const
Properties
- hashCode → int
-
The hash code for this object.
no setterinherited
- runtimeType → Type
-
A representation of the runtime type of the object.
no setterinherited
Methods
-
findBestPath<
T extends E> (WeightedWalkable< T> graph, T start, Goal<T> goal, {Tracer<T> ? tracer}) → (Path<T> , double) -
Returns an optimal path (and it's total cost) in
graphfromstartto a node that satisfiesgoal.inherited -
findBestPathExclusive<
T extends E> (WeightedWalkable< T> graph, T start, Goal<T> goal, {Tracer<T> ? tracer}) → (Path<T> , double) -
Returns an optimal path (and it's total cost) in
graphfromstartto a node that satisfiesgoal.override -
noSuchMethod(
Invocation invocation) → dynamic -
Invoked when a nonexistent method or property is accessed.
inherited
-
toString(
) → String -
A string representation of this object.
inherited
Operators
-
operator ==(
Object other) → bool -
The equality operator.
inherited