dijkstra

README

Go Dijkstra

Highly optimised implementation of the Dijkstra algorithm, used for find the shortest path between points of a graph.

Documentation

Full documentation available on GoDoc.

Documentation

Overview

Package dijkstra is an highly optimised implementation of the Dijkstra algorithm, used for find the shortest path between points of a graph.

A graph is a map of points and map to the neighbouring points in the graph and the cost to reach them. A trivial example of a graph definition is:

Graph{
	"a": {"b": 10, "c": 20},
	"b": {"a": 50},
	"c": {"b": 10, "a": 25},
}

Index

• type Graph
  • func (g Graph) Path(start, target string) (path []string, cost int, err error)
• type Queue
  • func NewQueue() *Queue
  • func (q *Queue) Get(key string) (priority int, ok bool)
  • func (q *Queue) IsEmpty() bool
  • func (q *Queue) Len() int
  • func (q *Queue) Less(i, j int) bool
  • func (q *Queue) Next() (key string, priority int)
  • func (q *Queue) Set(key string, priority int)
  • func (q *Queue) Swap(i, j int)

Examples

• Graph.Path

Types

type Graph

type Graph map[string]map[string]int

Graph is a rappresentation of how the points in our graph are connected between each other

func (Graph) Path

func (g Graph) Path(start, target string) (path []string, cost int, err error)

Path finds the shortest path between start and target, also returning the total cost of the found path.

Example

g := Graph{
	"a": {"b": 20, "c": 80},
	"b": {"a": 20, "c": 20},
	"c": {"a": 80, "b": 20},
}

path, cost, _ := g.Path("a", "c") // skipping error handling

fmt.Printf("path: %v, cost: %v", path, cost)

Output:

path: [a b c], cost: 40

type Queue

type Queue struct {
	// contains filtered or unexported fields
}

Queue is a basic priority queue implementation, where the node with the lowest priority is kept as first element in the queue

func NewQueue

func NewQueue() *Queue

NewQueue creates a new empty priority queue

func (*Queue) Get

func (q *Queue) Get(key string) (priority int, ok bool)

Get returns the priority of a passed key

func (*Queue) IsEmpty

func (q *Queue) IsEmpty() bool

IsEmpty returns true when the queue is empty

func (*Queue) Len

func (q *Queue) Len() int

Len is part of sort.Interface

func (*Queue) Less

func (q *Queue) Less(i, j int) bool

Less is part of sort.Interface

func (*Queue) Next

func (q *Queue) Next() (key string, priority int)

Next removes the first element from the queue and retuns it's key and priority

func (*Queue) Set

func (q *Queue) Set(key string, priority int)

Set updates or inserts a new key in the priority queue

func (*Queue) Swap

func (q *Queue) Swap(i, j int)

Swap is part of sort.Interface