去吧，Dijkstra算法：打印出来的路径，而不仅仅是计算的最短距离 [英] Go, Dijkstra : print out the path, not just calculate the shortest distance

问题描述

围棋，Dijkstra算法：打印出来的路径，而不仅仅是计算的最短距离

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

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

不过，这将是无用的，如果我不能打印出的路径。 随着大量指针的事情，我无法弄清楚如何打印出需要最少量的权重的最终路径。

总之，我怎么不仅可以找到最短的距离，而且打印出的最短路径上这个给定的code？

链接是在这里：

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

和的code中的片段是如下：

 常量MAXWEIGHT = 1000000

键入MinDistanceFromSource图[*顶点] INT

FUNC（G *图表）Dijks（StartSource，TargetSource的*顶点）MinDistanceFromSource {
  D：=使得（MinDistanceFromSource）
  为_，顶点：=范围G.VertexArray {
    D [顶] = MAXWEIGHT
  }
  D [StartSource] = 0

  边缘：=范围StartSource.GetAdEdg（）{
    D [edge.Destination] = edge.Weight
  }
  计算（StartSource，TargetSource的，D）
  返回ð
}

FUNC计算（StartSource，TargetSource的*顶点，D MinDistanceFromSource）{
  边缘：=范围StartSource.GetAdEdg（）{
    如果D [edge.Destination]≥ D [edge.Source] + edge.Weight {
      D [edge.Destination] = D [edge.Source] + edge.Weight
    }否则，如果D [edge.Destination] LT; D [edge.Source] + edge.Weight {
      继续
    }
    计算（edge.Destination，TargetSource的，D）
  }
}
 

我做了一件与阵列，看看有什么正在更新。

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

这给MS

  [A- D 1和D D-＆GT; e E-＆GT;˚FF-＆GT;吨B-＆GT; e E- D 1和D E-＆GT;˚FF- ＆GT; T]
 

解决方案

在这里调整的新路径距离

 如果D [edge.Destination] GT; D [edge.Source] + edge.Weight {
      D [edge.Destination] = D [edge.Source] + edge.Weight
 

设置一些数组元素（例如， P 为父），以点说，你来目标从来源。

  P [edge.Destination] = edge.Source
 

算法结束

在，在这个阵列中的每个顶点都会有predecessor从开始顶点领先的道路上。

PS。 OK，不与阵列和指数...

添加一个新的领域 $ P $光伏的顶点：

 类型的顶点结构{
    ID字符串
    参观布尔
    AdjEdge [] *边缘
    preV *顶点
}
 

当调节距离：

 如果D [edge.Destination] GT; D [edge.Source] + edge.Weight {
    D [edge.Destination] = D [edge.Source] + edge.Weight
    edge.Destination。preV = edge.Source
 

而当你显示结果：

 的vertex1，距离1：=范围distmap1 {
    fmt.Println（vertex1.Id，=，距离1）
    如果vertex1。preV！=零{
        fmt.Println（vertex1.Id， - ＆gt;中，vertex1 prev.Id。）
    }
}
 

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]

解决方案

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

这篇关于去吧，Dijkstra算法：打印出来的路径，而不仅仅是计算的最短距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！