去，Dijkstra：打印出路径，而不仅仅是计算最短距离

Question

去吧，Dijkstra：打印出路径，而不仅仅是计算最短距离。

http://play.golang.org/p/A2jnzKcbWD

我能够使用 Dijkstra 算法找到最短距离，也许不是。代码可以在这里找到。

但是如果我不能打印出路径就没有用了。由于有很多指针，我无法弄清楚如何打印出权重最少的最终路径。

简而言之，我如何不仅找到最短距离，而且还要在给定的代码上打印出最短路径？

链接在这里：

http://play.golang.org/p/A2jnzKcbWD

代码片段如下：

const MAXWEIGHT = 1000000

type MinDistanceFromSource map[*Vertex]int

func (G *Graph) Dijks(StartSource, TargetSource *Vertex) MinDistanceFromSource {

  D := make(MinDistanceFromSource)

  for _, vertex := range G.VertexArray {

    D[vertex] = MAXWEIGHT

  }

  D[StartSource] = 0

  for edge := range StartSource.GetAdEdg() {

    D[edge.Destination] = edge.Weight

  }

  CalculateD(StartSource, TargetSource, D)

  return D

}

func CalculateD(StartSource, TargetSource *Vertex, D MinDistanceFromSource) {

  for edge := range StartSource.GetAdEdg() {

    if D[edge.Destination] > D[edge.Source]+edge.Weight {

      D[edge.Destination] = D[edge.Source] + edge.Weight

    } else if D[edge.Destination] < D[edge.Source]+edge.Weight {

      continue

    }

    CalculateD(edge.Destination, TargetSource, D)

  }

}

我对数组做了一些事情来查看正在更新的内容。

http://play.golang.org/p/bRXYjnIGxy

这给了 ms

   [A->D D->E E->F F->T B->E E->D E->F F->T]