Go, Dijkstra : print out the path, not just calculate the shortest distance
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)
}
}
![Admin](/assets/logo_square_200-5d0d61d6853298bd2a4fe063103715b4daf2819fc21225efa21dfb93e61952ea.png)
Admin
Updated on June 18, 2022Comments
-
Admin about 2 years
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]
-
Admin over 10 yearsCan you explain in more detail? What do you mean by Set some array element? With what should I initialize the array? And P is an array then how can the index be the Vertex type? Thanks!@
-
chill over 10 yearsCheck the answer, I corrected it a bit. You initialize the array with some invalid vertex index.
-
Admin over 10 yearsHm is this what you talking about ? play.golang.org/p/TOlvZUwO5y This gives me non-integer slice index edge.Destination
-
Admin over 10 yearsI did similar thing, but still can't combine these results play.golang.org/p/bRXYjnIGxy