Go,Dijkstra:打印出路径,而不仅仅是计算最短距离

Question

Go,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]

Answer 1

在此处调整新路径距离时

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

设置一些数组元素(比如,P为"父"),以点说,你来Destination的Source.

P[edge.Destination] = edge.Source

算法结束后,在此数组中,每个顶点将在从起始顶点开始的路径上具有其前任.

PS.好的,不是数组和索引......

Prev向Vertex 添加一个新字段:

type Vertex struct {
    Id      string
    Visited bool
    AdjEdge []*Edge
    Prev *Vertex
}

调整距离时:

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

当您显示结果时:

for vertex1, distance1 := range distmap1 {
    fmt.Println(vertex1.Id, "=", distance1)
    if vertex1.Prev != nil {
        fmt.Println (vertex1.Id, " -> ", vertex1.Prev.Id)
    }
}