迪杰斯特拉

数据结构、离散数学、计算机网络、算法，这些课都讲过这个算法，再加上我大一的时候看的《图解算法》，对迪杰斯特拉已经很熟悉了。

戴克斯特拉算法（英语：Dijkstra’s algorithm），又译迪杰斯特拉算法，亦可不音译而称为Dijkstra算法[6]，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表[7][8][9]。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图[9]的单源最短路径问题[10][1][2]。

edges为一个二维数组，假设edge为其中的元素，edge[0]和edge[1]表示一条有向边上的两个节点，edge[2]表示这条边的权重。

const INFINITY = math.MaxInt64

func Dijkstra(edges [][]int, n int, k int) int {
   D := make(map[int]int)  // shortest path from k to other nodes
   S := make(map[int]bool) // nodes whose shortest path is already calculated

   // initialize
   for i := 1; i <= n; i++ {
      D[i] = INFINITY
   }
   D[k] = 0
   DISTANCE := make(map[string]int)
   for _, edge := range edges {
      DISTANCE[strconv.Itoa(edge[0])+" "+strconv.Itoa(edge[1])] = edge[2]
   }

   for {
      // the nearest node to source node which is not in set S
      u := extractMin(D, S)
      if u == -1 {
         break
      }
      S[u] = true
      for v, dist := range D {
         if _, ok := S[v]; !ok {
            uv := edge(u, v, DISTANCE)
            if uv != -1 {
               if D[u]+uv < dist {
                  D[v] = D[u] + uv
               }
            }
         }
      }
   }
}

// distance from u to v, if there is no path, return -1
func edge(u, v int, distance map[string]int) int {
   d, ok := distance[strconv.Itoa(u)+" "+strconv.Itoa(v)]
   if !ok {
      return -1
   }
   return d
}

// the nearest node to source node which is not in set S, if not found, return -1
func extractMin(D map[int]int, S map[int]bool) int {
   minDistance := INFINITY
   ans := -1
   for node, distance := range D {
      if _, ok := S[node]; !ok {
         if distance < minDistance {
            ans = node
            minDistance = distance
         }
      }
   }
   return ans
}