# Hi, I'm Ataias Reis

Programmer, made in Brazil, Alma mater University of Brasilia

# 30 days of code in Go: Day 24 - Djikstra's algorithm

Hi there! Today I implemented Djikstra’s algorithm to find the minimum path between one source vertex and all the other vertices in the graph. This algorithm was devised in 1956 by the Dutch computer scientist Edsger W. Djikstra. It is quite fast having a complexity of $O(n\log n)$ when implemented with an auxiliary heap structure.

To implement the heap in Go, I made use of the package heap. The package website also has an example of how to use and mine is basically a copy of it. I just changed one line. The code is available below. The graph structure was made basically with maps.

package main

import (
"container/heap"
"fmt"
"time"
)

// An Item is something we manage
// in a priority queue.
type Item struct {
// a node of a graph
value    *Node
// The priority of the item in the queue.
priority int
// The index of the item in the heap.
index int
}

// A PriorityQueue implements
//heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}

// update modifies the priority
// and value of an Item in the queue.
func (pq *PriorityQueue) update(
item *Item, value *Node, priority int) {

item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}

type Node struct {
// beginning of vertex
Id    int
// map of end vertex to weight
Edges map[int]int
}

// input is a map of vertex id to node pointer
// and the source vertex
// there are outputs: distances of
// each vertex to the source and
// the previous node that a vertex needs to go
// to follow the best path
func Dijkstra(nodes map[int]*Node, source int)
(map[int]int, map[int]int) {
// will be used for heap
Q := make(PriorityQueue, len(nodes))
// maintain reference to all items
heapItems := make(PriorityQueue, len(nodes))
distances := make(map[int]int)
previous := make(map[int]int)

// distance from source to source is 0
distances[source] = 0

for k, v := range nodes {
if k != source {
// unknown distance
distances[k] = 1000000
// undefined
previous[k] = -1
}
Q[k-1] = &Item{
value:    v,
priority: distances[k],
index:    k - 1}
heapItems[k-1] = Q[k-1]
}

heap.Init(&Q)

for Q.Len() > 0 {
item := heap.Pop(&Q).(*Item)
node := item.value
for end, weight := range node.Edges {
alt := item.priority + weight
if alt < distances[end] {
distances[end] = alt
previous[end] = node.Id
Q.update(
heapItems[end-1], nodes[end], alt)
}
}
}

return distances, previous
}

func CreateEdge(
nodes map[int]*Node, begin, end int, weight int) {

if nodes[begin] == nil {
nodes[begin] = &Node{
Id:    begin,
Edges: make(map[int]int)}
}

if nodes[end] == nil {
nodes[end] = &Node{
Id:    end,
Edges: make(map[int]int)}
}

nodes[begin].Edges[end] = weight
}

func main() {
start := time.Now()

nodes := make(map[int]*Node)

begin := 0
end := 0
weight := 0
lines := 0
value := 0
for {
if value == 0 {
n, _ := fmt.Scanf("%d", &begin)
if n == 0 {
break
}
} else {
begin = end
}
lines += 1
value = 0
for {
n, _ := fmt.Scanf("%d,%d", &end, &weight)
if n == 0 {
break
}
if n == 1 {
// if we read only one value, this is
// from the next line
value = end
break
}
CreateEdge(nodes, begin, end, weight)
}
}

elapsed := time.Since(start)
fmt.Printf("IO Took %s\n", elapsed)

start = time.Now()
distances, _ := Dijkstra(nodes, 1)
for i := 1; i <= len(nodes); i++ {
fmt.Printf("Node: %d; Distance: %d\n",
i, distances[i])
}
elapsed = time.Since(start)
fmt.Printf("Computation Took %s\n", elapsed)

}


### Example

#### Input

1	2,1	8,2
2	1,1	3,1
3	2,1	4,1
4	3,1	5,1
5	4,1	6,1
6	5,1	7,1
7	6,1	8,1
8	7,1	1,2


#### Output

Lines read: 8
IO Took 1.007893ms
Node: 1; Distance: 0
Node: 2; Distance: 1
Node: 3; Distance: 2
Node: 4; Distance: 3
Node: 5; Distance: 4
Node: 6; Distance: 4
Node: 7; Distance: 3
Node: 8; Distance: 2
Computation Took 25.511µs


If you have any suggestions or comments, let me know! Thanks for reading!