Documentation
¶
Overview ¶
Package Dijkstra provides an implementation of Dijkstra Algorithm to find the shortest path in directed graph.
The Dijkstra Algorithm traverses a graph object implementing the dijkstrastruct.GraphObject interface to find the shortest path; the only limitation is that all the edges' weights must be non-negative. The returned path, an instance of DijkstraPath struct, is a loopless path going from the starting node to the destination; it can be computed using either the "vanilla" Dijkstra algorithm or a bidirectional search algorithm.
Index ¶
- Constants
- func BiDirDijkstra(graph dijkstrastructs.GraphObject, startNode, endNode string, ...) (dijkstrapath.DijkstraPath, bool)
- func Dijkstra(graph dijkstrastructs.GraphObject, startNode, endNode string, ...) (dijkstrapath.DijkstraPath, bool)
- func SearchPath(graph dijkstrastructs.GraphObject, startNode, endNode string, searchType int) (dijkstrapath.DijkstraPath, bool)
- type DijkstraQueue
Constants ¶
const ( VANILLA = iota // Use "vanilla" Dijkstra algorithm BIDIR // Use bi-directional search algorithm )
Variables ¶
This section is empty.
Functions ¶
func BiDirDijkstra ¶
func SearchPath ¶
func SearchPath(graph dijkstrastructs.GraphObject, startNode, endNode string, searchType int) (dijkstrapath.DijkstraPath, bool)
Dijkstra returns the shortest path within the provided graph object that goes from startNode to endNode nodes. searchType parameter defines the type of algorithm to use.
Types ¶
type DijkstraQueue ¶
type DijkstraQueue []*dijkstrastructs.DijkstraCandidate
DijkstraQueue is a collecition of DijkstraCandidate elements. It implements the heap.Interface interface to be used as a heap.
func (DijkstraQueue) Len ¶
func (pq DijkstraQueue) Len() int
func (DijkstraQueue) Less ¶
func (pq DijkstraQueue) Less(i, j int) bool
func (*DijkstraQueue) Pop ¶
func (pq *DijkstraQueue) Pop() interface{}
func (*DijkstraQueue) Push ¶
func (pq *DijkstraQueue) Push(x interface{})
func (DijkstraQueue) Swap ¶
func (pq DijkstraQueue) Swap(i, j int)
Source Files