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