shortestpath

README

shortestpathalgorithms

Dijkstra, Bellman-Ford, A* shortest path algorithms written in Golang.

Binary heap, tools and unittests are included in this project aswell.

Install this package via: go get github.com/stepulak/shortestpathalgorithms

Feel free to pull request if you find a bug!

Documentation

Index

• type BinaryHeap
  • func NewBinaryHeap[TValue any](cmp CompareFunc[TValue]) *BinaryHeap[TValue]
  • func (h *BinaryHeap[TValue]) Contains(valueToFind TValue, cmp CompareFunc[TValue]) bool
  • func (h *BinaryHeap[TValue]) Head() (TValue, bool)
  • func (h *BinaryHeap[TValue]) Pop() (TValue, bool)
  • func (h *BinaryHeap[TValue]) Push(value TValue)
  • func (h *BinaryHeap[TValue]) Size() int
• type CompareFunc
• type Edge
• type EdgeList
• type Graph
  • func NewGraph[TValue any]() *Graph[TValue]
  • func (g *Graph[TValue]) AStar(start, end *Node[TValue], h func(n *Node[TValue]) float64) (NodeList[TValue], error)
  • func (g *Graph[TValue]) AddEdge(from, to *Node[TValue], distance float64) *Edge[TValue]
  • func (g *Graph[TValue]) AddNode(value TValue) *Node[TValue]
  • func (g *Graph[TValue]) BellmanFord(source *Node[TValue]) (Predecessors[TValue], error)
  • func (g *Graph[TValue]) Dijkstra(source *Node[TValue]) (Predecessors[TValue], error)
  • func (g *Graph[TValue]) Size() int
  • func (g Graph[TValue]) ToDot(value func(TValue) string) (string, error)
• type Node
• type NodeList
• type Predecessors
  • func (p Predecessors[TValue]) Get(node *Node[TValue]) *Node[TValue]
  • func (p Predecessors[TValue]) GetShortestPath(nodeEnd *Node[TValue]) NodeList[TValue]
  • func (p Predecessors[TValue]) Set(from, to *Node[TValue])

Types

type BinaryHeap

type BinaryHeap[TValue any] struct {
	Tree       []TValue
	Comparator CompareFunc[TValue]
}

func NewBinaryHeap

func NewBinaryHeap[TValue any](cmp CompareFunc[TValue]) *BinaryHeap[TValue]

func (*BinaryHeap[TValue]) Contains

func (h *BinaryHeap[TValue]) Contains(valueToFind TValue, cmp CompareFunc[TValue]) bool

func (*BinaryHeap[TValue]) Head

func (h *BinaryHeap[TValue]) Head() (TValue, bool)

func (*BinaryHeap[TValue]) Pop

func (h *BinaryHeap[TValue]) Pop() (TValue, bool)

Pop head (root) value

func (*BinaryHeap[TValue]) Push

func (h *BinaryHeap[TValue]) Push(value TValue)

Push value to the heap

func (*BinaryHeap[TValue]) Size

func (h *BinaryHeap[TValue]) Size() int

type CompareFunc

type CompareFunc[TValue any] func(a, b TValue) bool

type Edge

type Edge[TValue any] struct {
	From     *Node[TValue]
	To       *Node[TValue]
	Distance float64
}

type EdgeList

type EdgeList[TValue any] []*Edge[TValue]

type Graph

type Graph[TValue any] struct {
	NodeCounter int
	Nodes       NodeList[TValue]
}

func NewGraph

func NewGraph[TValue any]() *Graph[TValue]

func (*Graph[TValue]) AStar

func (g *Graph[TValue]) AStar(start, end *Node[TValue], h func(n *Node[TValue]) float64) (NodeList[TValue], error)

func (*Graph[TValue]) AddEdge

func (g *Graph[TValue]) AddEdge(from, to *Node[TValue], distance float64) *Edge[TValue]

func (*Graph[TValue]) AddNode

func (g *Graph[TValue]) AddNode(value TValue) *Node[TValue]

func (*Graph[TValue]) BellmanFord

func (g *Graph[TValue]) BellmanFord(source *Node[TValue]) (Predecessors[TValue], error)

func (*Graph[TValue]) Dijkstra

func (g *Graph[TValue]) Dijkstra(source *Node[TValue]) (Predecessors[TValue], error)

func (*Graph[TValue]) Size

func (g *Graph[TValue]) Size() int

func (Graph[TValue]) ToDot

func (g Graph[TValue]) ToDot(value func(TValue) string) (string, error)

type Node

type Node[TValue any] struct {
	Id    int
	Value TValue
	Edges EdgeList[TValue]
}

type NodeList

type NodeList[TValue any] []*Node[TValue]

type Predecessors

type Predecessors[TValue any] map[int]*Node[TValue]

Look up table to find a node's predecessor Key: Node.Id of node A Value: *Node of node B Result: Edge from node A to node B

func (Predecessors[TValue]) Get

func (p Predecessors[TValue]) Get(node *Node[TValue]) *Node[TValue]

func (Predecessors[TValue]) GetShortestPath

func (p Predecessors[TValue]) GetShortestPath(nodeEnd *Node[TValue]) NodeList[TValue]

Get the longest shortest path from starting node to nodeEnd

func (Predecessors[TValue]) Set

func (p Predecessors[TValue]) Set(from, to *Node[TValue])