dijkstra_sample.go

package main

import "fmt"

const (
  StationNumber = 6
  StartStation = 0
)

var (
  stations = []string { "Yokohama", "Musashikosugi", "Shinagawa", "Shibuya", "Shimbashi", "Tameikesannno" }
  currentCost = [StationNumber]int { -1, -1, -1, -1, -1, -1 }
  fix [StationNumber]int
  matrix = [StationNumber][StationNumber]int {
    {0, 12, 28, 0, 0, 0},
    {12, 0, 10, 13, 0, 0},
    {28, 10, 0, 11, 7, 0},
    {0, 13, 11, 0, 0, 9},
    {0, 0, 7, 0, 0, 4},
    {0, 0, 0, 9, 4, 0},
  }
)

func main() {
  var min_station, min_time, new_time int
  currentCost[0] = 0

  for {
    min_time = -1
    
    for i := 0; i < StationNumber; i++ {
      if fix[i] == 0 && currentCost[i] != -1 {
        if min_time == -1 || min_time > currentCost[i] {
          min_time = currentCost[i]
          min_station = i
        }
      }
    }

    if min_time == -1 { break }

    for i := 0; i < StationNumber; i++ {
      if fix[i] == 0 && matrix[min_station][i] > 0 {
        new_time = min_time + matrix[min_station][i]
    
        if currentCost[i] == -1 || currentCost[i] > new_time {
          currentCost[i] = new_time
        }
      }
    }
    fix[min_station] = 1
  }

  for i := 0; i < StationNumber; i++ {
    fmt.Printf("%s -> %s: ", stations[StartStation], stations[i])
    fmt.Printf("%d\n", currentCost[i])
  }
}