dijkstra

Documentation

Index

• Variables
• func AddOverflow[T Numeric](a, b T) (sum T, overflow bool)
• func BuildRoute[K comparable](start, end K, prevs map[K]K) []K
• func Dijkstra[K comparable, D Numeric](start K, neighbors func(K) ([]K, []D), isTarget func(K) bool) (map[K]D, map[K]K, error)
• func TargetAll[K comparable](target ...K) func(K) bool
• func TargetAny[K comparable](target ...K) func(K) bool
• type IndexedHeap
  • func NewIndexedHeap[K comparable, D Numeric]() *IndexedHeap[K, D]
  • func (ih *IndexedHeap[K, D]) ExtractMin() (K, D)
  • func (ih *IndexedHeap[K, D]) Len() int
  • func (ih *IndexedHeap[K, D]) ReducePriority(key K, distance D) bool
• type Numeric

Variables

var (
	ErrOverflow          = errors.New("Distance addition overflow")
	ErrNegativeDistance  = errors.New("Negative distance")
	ErrNeighborsMismatch = errors.New("Neighbors slice lengths do not match")
)

Functions

func AddOverflow

func AddOverflow[T Numeric](a, b T) (sum T, overflow bool)

AddOverflow adds two numbers with overflow detection. For floats, it also returns overflow==true if there is a NaN input, which is deemed right in the context of Dijkstra.

func BuildRoute

func BuildRoute[K comparable](start, end K, prevs map[K]K) []K

BuildRoute takes a "prevs" map from Dijkstra and builds a list of nodes starting at start, ending at end, which is a possible shortest path from start to end. If there is no way to reach start from end following links in prevs[], BuildRoute returns nil.

func Dijkstra

func Dijkstra[K comparable, D Numeric](start K, neighbors func(K) ([]K, []D),
	isTarget func(K) bool) (map[K]D, map[K]K, error)

Dijkstra runs Dijkstra's shortest path finding against a graph, from the starting point start to all graph's vertices or to the nearest target detected by optional isTarget function.

To avoid requiring any particular graph representation, it accepts the neighbors function, that should return all vertexes directly reachable from the argument together with distances to them, in parallel slices.

The algorithm stops when there are no new vertexes to reach, or when a non-nil isTarget returns true for a vertex with known shortest distance.

Return values: map[K]D mapping each vertex encountered by the algorithm along the way to the shortest path from start to this vertex, map[K]K mapping each vertex (except start) to the previous vertex along one of the shortest paths, allowing to build an example shortest path from start to any vertex encountered.

On errors, ErrNeighborsMismatch, ErrNegativeDistance, ErrOverflow can be returned (with nil maps)

func TargetAll

func TargetAll[K comparable](target ...K) func(K) bool

TargetAll creates a target-filtering closure for Dijkstra, returning true when all specified targets were reached. Mutates a shared state inside, so should constructed once per call to Dijkstra.

Note: with no arguments, the closure returns true immediately, so Dijkstra will stop after settling the start node. This follows from vacuous truth but may be surprising.

func TargetAny

func TargetAny[K comparable](target ...K) func(K) bool

TargetAny creates a target-filtering closure for Dijkstra, returning true when the argument is present within a slice

Types

type IndexedHeap

type IndexedHeap[K comparable, D Numeric] struct {
	// contains filtered or unexported fields
}

IndexedHeap stores keys of type K with priorities of type D. Specially designed for Dijkstra algorithm.

func NewIndexedHeap

func NewIndexedHeap[K comparable, D Numeric]() *IndexedHeap[K, D]

NewIndexedHeap creates and returns a new, empty IndexedHeap

func (*IndexedHeap[K, D]) ExtractMin

func (ih *IndexedHeap[K, D]) ExtractMin() (K, D)

ExtractMin pops the minimal-distance item, returning key and distance

func (*IndexedHeap[K, D]) Len

func (ih *IndexedHeap[K, D]) Len() int

Len returns item count for IndexedHeap

func (*IndexedHeap[K, D]) ReducePriority

func (ih *IndexedHeap[K, D]) ReducePriority(key K, distance D) bool

ReducePriority either adds an item (if it is not there) or lowers existing item's distance if given distance is less then the old one. Returns true iff the distance was indeed reduced. Conceptually, the distance to an item which is not there is infinity (hence reduced when the item is added).

type Numeric

type Numeric interface {
	~uint64 | ~uint32 | ~uint16 | ~uint8 | ~uint | ~uintptr |
		~int64 | ~int32 | ~int16 | ~int8 | ~int |
		~float64 | ~float32
}