dijkstra

package

v0.0.0-...-09d313d Latest Latest Go to latest Published: Nov 8, 2016 License: AGPL-3.0 Imports: 4 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/iocat/cs344

Links

Open Source Insights

Documentation ¶

Index ¶

type SPTree
- func Find(g *graph.Graph, source int) SPTree
- func (t SPTree) Path(toVertex int) SPTree
- func (t SPTree) String() string
type Vertex

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

Types ¶

type SPTree ¶

type SPTree []*Vertex

SPTree represents the shortest path tree

func Find ¶

func Find(g *graph.Graph, source int) SPTree

Find builds the shortest path tree using Dijkstra algorithm. A greedy algorithm that gradually builds the shortest path tree

The runtime is O((|V|+|E|)*log|E|) where |V|log|E| accounts for heap.Fix whenever we check an out-going edge. And |E|log|E| accounts for heap.Pop to get the smallest cost vertex.

func (SPTree) Path ¶

func (t SPTree) Path(toVertex int) SPTree

Path returns the shortest path from the source vertex to a chosen vertex

func (SPTree) String ¶

func (t SPTree) String() string

type Vertex ¶

type Vertex struct {
	ID     int /* The id of this node */
	Parent int /* The ID of the parent vertex, -1 for the source */
	TotalC int /* The total cost from source node */
}

Vertex represents the non-visited vertex which is stored in the minimum cost priority heap

Source Files ¶

View all Source files

dijkstra.go

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL