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

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)

}