algorithm - 计算 Dijkstra 算法的特定边数

Question

你好，我目前正在研究 Dijkstras 算法。我想计算为更改下一条边的成本等而选择的特定边的数量。我在添加选择特定边的次数时遇到问题。我链接了部分代码。

Edge dirC = new Edge("d" + nodes.get(i * ds.columns + j), nodes.get(i * ds.columns + j), nodes.get((i + 1) * ds.columns + j), downcost1);
edges.add(dirC);

在这部分中添加了一个特定的边“dirC”。我想添加一个“dicCcount”，然后取回计数器的值，以便在该部分运行后在 if 语句中使用它。 Edge 类看起来像这样。

package autonavigate;

public class Edge  {
  private final String id; 
  private final Vertex source;
  private final Vertex destination;
  private final double weight; 
  
  public Edge(String id, Vertex source, Vertex destination, double weight) {
    this.id = id;
    this.source = source;
    this.destination = destination;
    this.weight = weight;
  }
  
  public String getId() {
    return id;
  }
  
  public Vertex getDestination() {
    return destination;
  }

  public Vertex getSource() {
    return source;
  }
  public double getWeight() {
    return weight;
  }
  
  @Override
  public String toString() {
    return source + " " + destination;
  }
 } 

我已经尝试解决这个问题好几个小时了，但我不知道该怎么做。这不是家庭作业，而是我为遥控车完成的程序 :)。

有什么建议吗？

Answer 1

如果我对您的问题的理解正确，您可能会考虑以下其中一项:

1. 一个字典数据结构(在 Edge 数据类型之外定义)来跟踪选定的边，每次选择边时都会增加计数器(作为值)；这将在您跟踪图表时更新(它应该在跟踪算法结束时处理掉)
2. 对 Edge 数据类型的扩展，它实现了被“选择”的行为，并在跟踪运行期间在内部跟踪它被访问的次数(可以选择重置其内部计数器)