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

Question

Go, Dijkstra : print out the path, not just calculate the shortest distance.

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

I was able to find the shortest distance using Dijkstra algorithm, maybe not. The code can be found here.

But it would be useless if I can't print out the path. With a lot of pointers going on, I can't figure out how to print out the final path that takes the least amount of weights.

In short, how do I not only find the shortest distance, but also print out the shortest path on this given code?

The link is here:

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

And the snippet of the code is below:

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)
  }
}

I did something with array to see what is being updated.

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

This gives ms

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

Answer 1

When you adjust the new path distance here

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

Set some array element (say, P for "parent") to point that you have come to Destination from Source.

P[edge.Destination] = edge.Source

After the algorithm ends, in this array each vertex will have its predecessor on the path leading from the starting vertex.

PS. OK, not with arrays and indices ...

Add a new field Prev to the Vertex:

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

When adjusting distance:

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

And when you display the results:

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