我using this exact code为了这。我稍微修改了一下。到目前为止，我向 calculateShortestDistances() 方法添加了开始和结束节点索引。也是用于收集路径节点索引的路径 ArrayList。另外:Java 新手...

如何收集路径 ArrayList中节点的索引？

我无法在某种程度上提出解决方案，我什至不肯定这段代码可以做我想做的事。我只有直觉，时间不多。

我尝试过的:

• 将 nextNode 值添加到列表中，如果不是则将其删除 更短的距离。
• 将 neighborIndex 添加到列表中，如果距离不短则将其删除。
• 我用 ArrayList 创建了一个 Path.java，但没有任何进展(这是一个带有名为 path 的公共(public)变量的类)，但没有任何进展。

主.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 变量，这样我就可以告诉它我要走的路径。我还创建了一个公共(public) path ArrayList，我打算在其中收集路径。

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 算法是如何工作的，我理解这个概念，我可以在纸上做。但是收集路径超出了我的范围。

最佳答案

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

我修改如下(我只放了相关的部分)

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

  [...]
  private int predecessor;

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

图形.java 在这里，我创建了 calculatePath() 和 getPath() 方法。 calculatePath() 执行评论者告诉我的操作。 getPath() 返回 ArrayLists 供其他人使用。

  [...]

  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);
[...]

我知道它显示的是倒退的路径，但这不是问题，因为我总能反转它。关键是:我不仅有节点到节点的距离，还有通过节点的路径。感谢您的帮助。

关于java - Dijkstra 的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57347731/