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)
    }
  }

  fmt.Printf("Lines read: %d\n", lines)

  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!

Tags
comments powered by Disqus