0

我正在开发一个项目，以在 java 中实现 Dijkstra 的最短路径算法。我在我的程序中使用了这个版本：LINK

我的程序需要一个源并给我这样的输出：

Distance to PE Hall: 0.0 Path: [PE Hall]

Distance to Reception: 1.0 Path: [PE Hall, Reception]

Distance to Stairs: 3.0 Path: [PE Hall, Stairs]

Distance to Refectory: 7.0 Path: [PE Hall, Stairs, Refectory]

我真正想要的是输出给我路径中每个节点之间的距离，例如：

Distance to Refectory: 7.0 Path: [PE Hall 0.0, Stairs 3.0, Refectory 4.0]

-

更新

我通过在每个顶点中添加一个“前一个顶点”变量来实现程序存储路径。我的输出正是我想要的，但是，我的方法通过在路径上迭代返回的距离是不正确的。

Target = E250 Distance = 0.0 {E250=0.0}
Target = D Distance = 10.0 {E250=0.0, D=10.0}
Target = C250Trans Distance = 35.0 {E250=0.0, C250Trans=10.0, D=10.0}

这是我用来创建一个数组列表的方法，其中包含每个点之间的路径和距离

public static ArrayList<String> getShortestPaths(Vertex target)
  {
      ArrayList<String> path = new ArrayList<String>();
      for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        {   
             path.add(vertex.name + "=" + vertex.getDistFromPrev());
        }
      Collections.reverse(path);
      return path;
  }

这是我用来获取路径中每个点之间的距离的方法，包含在顶点类中：

 public double getDistFromPrev()
{
    double weight = 0.;
    for(Edge e : adjacencies){
        if(e.target == this.previous){
            weight = e.weight;
        }
    }
    return weight;
}

这是供参考的距离矩阵：

E250 - D = 10

D - C250 = 25

如果有人可以澄清为什么使用每个顶点的previous变量迭代路径会返回不正确的边缘距离，这对我有很大帮助。

4

2 回答 2

0

让s成为路径的起始顶点，d(v)成为顶点v到顶点的距离，s让e = w->v成为路径的边缘。那么 的长度e为d(v) - d(w)。在您的示例中，边缘的长度Stairs -> Refectory是7.0 - 3.0 = 4.0

于 2013-03-26T14:27:54.863 回答
0

你知道路径：

PE Hall, Stairs, Refectory

您还知道到路径中每个位置的距离：

PE Hall: 0.0 
Reception: 1.0 
Stairs: 3.0 
Refectory: 7.0

Dijkstra为您提供您想要的信息，您只需要适当地“格式化”它（例如，编写一个组合数据的小助手函数并在 Dijkstra 完成后调用您的助手）。

于 2013-03-26T14:16:51.830 回答