Dijkstra的最短路径

Question

我为此使用了确切的代码。我做了一点修改。到目前为止，我已向该calculateShortestDistances()方法添加了起始和结束节点索引。还有用于收集路径节点索引的路径ArrayList。另外：Java的新手...

如何收集pathArrayList 中节点的索引？

我只是无法提出一个解决方案，即使我对此代码不能满足我的要求也不满意。我只有直觉，很少有时间。

我试过的

• 将nextNode值添加到列表中，如果距离不短，则将其删除。
• 将neighbourIndex添加到列表中，如果距离不短，则将其删除。
• 我用ArrayList创建了一个Path.java，但是没有成功（这是一个带有名为path的公共变量的类），但是没有成功。

Main.java：

public class Main {
  public static void main(String[] args) {
    Edge[] edges = {
      new Edge(0, 2, 1), new Edge(0, 3, 4), new Edge(0, 4, 2),
      new Edge(0, 1, 3), new Edge(1, 3, 2), new Edge(1, 4, 3),
      new Edge(1, 5, 1), new Edge(2, 4, 1), new Edge(3, 5, 4),
      new Edge(4, 5, 2), new Edge(4, 6, 7), new Edge(4, 7, 2),
      new Edge(5, 6, 4), new Edge(6, 7, 5)
    };
    Graph g = new Graph(edges);
    g.calculateShortestDistances(4,6);
    g.printResult(); // let's try it !

    System.out.println(g.path);
  }
}

Graph.java：

这是Graph.java文件。在这里，我添加了一个sAt和eAt变量，因此可以告诉它我要走的路径。我还创建了一个公共pathArrayList，打算在其中收集路径。

import java.util.ArrayList;
// now we must create graph object and implement dijkstra algorithm
public class Graph {
  private Node[] nodes;
  private int noOfNodes;
  private Edge[] edges;
  private int noOfEdges;

  private int sAt;
  private int eAt;

  public ArrayList<Integer> path = new ArrayList<>();

  public Graph(Edge[] edges) {
    this.edges = edges;
    // create all nodes ready to be updated with the edges
    this.noOfNodes = calculateNoOfNodes(edges);
    this.nodes = new Node[this.noOfNodes];
    for (int n = 0; n < this.noOfNodes; n++) {
      this.nodes[n] = new Node();
    }
    // add all the edges to the nodes, each edge added to two nodes (to and from)
    this.noOfEdges = edges.length;
    for (int edgeToAdd = 0; edgeToAdd < this.noOfEdges; edgeToAdd++) {
      this.nodes[edges[edgeToAdd].getFromNodeIndex()].getEdges().add(edges[edgeToAdd]);
      this.nodes[edges[edgeToAdd].getToNodeIndex()].getEdges().add(edges[edgeToAdd]);
    }
  }
  private int calculateNoOfNodes(Edge[] edges) {
    int noOfNodes = 0;
    for (Edge e : edges) {
      if (e.getToNodeIndex() > noOfNodes)
        noOfNodes = e.getToNodeIndex();
      if (e.getFromNodeIndex() > noOfNodes)
        noOfNodes = e.getFromNodeIndex();
    }
    noOfNodes++;
    return noOfNodes;
  }

  public void calculateShortestDistances(int startAt, int endAt) {

    // node 0 as source
    this.sAt = startAt;
    this.eAt = endAt;
    this.nodes[startAt].setDistanceFromSource(0);
    int nextNode = startAt;
    // visit every node
    for (int i = 0; i < this.nodes.length; i++) {
      // loop around the edges of current node
      ArrayList<Edge> currentNodeEdges = this.nodes[nextNode].getEdges();

      for (int joinedEdge = 0; joinedEdge < currentNodeEdges.size(); joinedEdge++) {

        int neighbourIndex = currentNodeEdges.get(joinedEdge).getNeighbourIndex(nextNode);
        // only if not visited

        if (!this.nodes[neighbourIndex].isVisited()) {
          int tentative = this.nodes[nextNode].getDistanceFromSource() + currentNodeEdges.get(joinedEdge).getLength();

          if (tentative < nodes[neighbourIndex].getDistanceFromSource()) {
            nodes[neighbourIndex].setDistanceFromSource(tentative);



          }
        }

      }
      // all neighbours checked so node visited
      nodes[nextNode].setVisited(true);
      // next node must be with shortest distance
      nextNode = getNodeShortestDistanced();
   }
  }
  // now we're going to implement this method in next part !
  private int getNodeShortestDistanced() {
    int storedNodeIndex = 0;
    int storedDist = Integer.MAX_VALUE;
    for (int i = 0; i < this.nodes.length; i++) {
      int currentDist = this.nodes[i].getDistanceFromSource();

      if (!this.nodes[i].isVisited() && currentDist < storedDist) {
        storedDist = currentDist;
        storedNodeIndex = i;

      } 
    }
    return storedNodeIndex;
  }
  // display result
  public void printResult() {
    String output = "Number of nodes = " + this.noOfNodes;
    output += "\nNumber of edges = " + this.noOfEdges;

    output += "\nDistance from "+sAt+" to "+eAt+":" + nodes[eAt].getDistanceFromSource();

    System.out.println(output);
  }
  public Node[] getNodes() {
    return nodes;
  }
  public int getNoOfNodes() {
    return noOfNodes;
  }
  public Edge[] getEdges() {
    return edges;
  }
  public int getNoOfEdges() {
    return noOfEdges;
  }
}

另外，还有Edge.java和Node.java类。

Node.java：

import java.util.ArrayList;
public class Node {
  private int distanceFromSource = Integer.MAX_VALUE;
  private boolean visited;
  private ArrayList<Edge> edges = new ArrayList<Edge>(); // now we must create edges
  public int getDistanceFromSource() {
    return distanceFromSource;
  }
  public void setDistanceFromSource(int distanceFromSource) {
    this.distanceFromSource = distanceFromSource;
  }
  public boolean isVisited() {
    return visited;
  }
  public void setVisited(boolean visited) {
    this.visited = visited;
  }
  public ArrayList<Edge> getEdges() {
    return edges;
  }
  public void setEdges(ArrayList<Edge> edges) {
    this.edges = edges;
  }
}

Edge.java

public class Edge {
  private int fromNodeIndex;
  private int toNodeIndex;
  private int length;
  public Edge(int fromNodeIndex, int toNodeIndex, int length) {
    this.fromNodeIndex = fromNodeIndex;
    this.toNodeIndex = toNodeIndex;
    this.length = length;
  }
  public int getFromNodeIndex() {
    return fromNodeIndex;
  }
  public int getToNodeIndex() {
    return toNodeIndex;
  }
  public int getLength() {
    return length;
  }
  // determines the neighbouring node of a supplied node, based on the two nodes connected by this edge
  public int getNeighbourIndex(int nodeIndex) {
    if (this.fromNodeIndex == nodeIndex) {
      return this.toNodeIndex;
    } else {
      return this.fromNodeIndex;
   }
  }
}

我知道这看起来像是一项家庭作业。相信我不是。另一方面，我没有太多时间来完成它，这就是为什么我在周日要做。我也知道Dijkstra算法是如何工作的，我理解这个概念，我可以在纸上做到。但是，收集道路已经超越了我。

Answer 1

感谢Christian H. Kuhn和Second的评论，我设法想出了代码。

我修改如下（我只放入了相关部分）

Node.java 这里我添加了 asetPredecessor(Integer predecessor)和 agetPredecessor()方法来设置和获取私有变量的值predecessor（所以我也遵循原始代码的风格）。

  [...]
  private int predecessor;

  [...]
  public int getPredecessor(){
    return predecessor;
  }
  public void setPredecessor(int predecessor){
    this.predecessor = predecessor;
  }
  [...]

Graph.java 这里我创建了calculatePath()和getPath()方法。calculatePath()做评论者告诉我做的事情。getPath() 返回 ArrayList 供其他人使用。

  [...]

  private int sAt;
  private int eAt;

  private ArrayList<Integer> path = new ArrayList<Integer>();

  [...]

  public void calculateShortestDistances(int startAt, int endAt) {

  [...]
          if (tentative < nodes[neighbourIndex].getDistanceFromSource()) {
            nodes[neighbourIndex].setDistanceFromSource(tentative);
            nodes[neighbourIndex].setPredecessor(nextNode);
          }

  [...]
  public void calculatePath(){
        int nodeNow = eAt;

        while(nodeNow != sAt){
            path.add(nodes[nodeNow].getPredecessor());
            nodeNow = nodes[nodeNow].getPredecessor();

        }

    }

    public ArrayList<Integer> getPath(){

        return path;

    }
    [...]

Main.java所以我现在可以这样做：

[...]
Graph g = new Graph(edges);
g.calculateShortestDistances(5,8);
g.calculatePath();

String results =  "";

ArrayList<Integer> path = g.getPath();

System.out.println(path);
[...]

我知道它显示了向后的路径，但这不是问题，因为我总是可以反转它。要点是：我不仅有节点到节点的距离，还有通过节点的路径。感谢您的帮助。