Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NullHeuristic ¶
NullHeuristic is an admissible, consistent heuristic that will not speed up computation.
Types ¶
type Heuristic ¶
type Heuristic[Node comparable] func(x, y Node) float64
Heuristic returns an estimate of the cost of travelling between two nodes.
type HeuristicCoster ¶
type HeuristicCoster[Node comparable] interface { HeuristicCost(x, y Node) float64 }
HeuristicCoster can be implemented by a graph.Graph to provide a default cost heuristic for the graph.
type Shortest ¶
type Shortest[Node comparable] struct { // contains filtered or unexported fields }
Shortest is a shortest-path tree created by the BellmanFordFrom, DijkstraFrom or AStar single-source shortest path functions.
func AStar ¶
func AStar[Node comparable, Edge any](s, t Node, g graph.Graph[Node, Edge], h Heuristic[Node]) (path Shortest[Node], expanded int)
AStar finds the A*-shortest path from s to t in g using the heuristic h. The path and its cost are returned in a Shortest along with paths and costs to all nodes explored during the search. The number of expanded nodes is also returned. This value may help with heuristic tuning.
The path will be the shortest path if the heuristic is admissible. A heuristic is admissible if for any node, n, in the graph, the heuristic estimate of the cost of the path from n to t is less than or equal to the true cost of that path.
If h is nil, AStar will use the g.HeuristicCost method if g implements HeuristicCoster, falling back to NullHeuristic otherwise. If the graph does not implement Weighted, UniformCost is used. AStar will panic if g has an A*-reachable negative edge weight.
func (Shortest[Node]) From ¶
func (p Shortest[Node]) From() Node
From returns the starting node of the paths held by the Shortest.
type Weighting ¶
Weighting is a mapping between a pair of nodes and a weight. It follows the semantics of the Weighter interface.
func UniformCost ¶
func UniformCost[Node comparable, Edge any](g graph.Graph[Node, Edge]) Weighting[Edge]
UniformCost returns a Weighting that returns an edge cost of 1 for existing edges, zero for node identity and Inf for otherwise absent edges.
Source Files