path

Documentation

Index

• func NullHeuristic[Node any](_, _ Node) float64
• type Heuristic
• type HeuristicCoster
• type Shortest
  • func AStar[Node comparable, Edge any](s, t Node, g graph.Graph[Node, Edge], h Heuristic[Node]) (path Shortest[Node], expanded int)
  • func (p Shortest[Node]) From() Node
  • func (p Shortest[Node]) To(v Node) (path []Node, weight float64)
  • func (p Shortest[Node]) WeightTo(v Node) float64
• type Weighting
  • func UniformCost[Node comparable, Edge any](g graph.Graph[Node, Edge]) Weighting[Edge]

Functions

func NullHeuristic

func NullHeuristic[Node any](_, _ Node) float64

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.

func (Shortest[Node]) To

func (p Shortest[Node]) To(v Node) (path []Node, weight float64)

To returns a shortest path to v and the weight of the path. If the path to v includes a negative cycle, one pass through the cycle will be included in path, but any path leading into the negative cycle will be lost, and weight will be returned as -Inf.

func (Shortest[Node]) WeightTo

func (p Shortest[Node]) WeightTo(v Node) float64

WeightTo returns the weight of the minimum path to v. If the path to v includes a negative cycle, the returned weight will not reflect the true path weight.

type Weighting

type Weighting[Edge any] func(e Edge) float64

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.