Dijkstra 的最短路径

Question

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

的新手

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

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

我尝试了什么：

将 nextNode 值添加到列表中，如果不是则将其删除更短的距离。
将 neighbourIndex 添加到列表中，如果距离不短则将其删除。
我用 ArrayList 创建了一个 Path.java，但没有任何进展（它是一个 class，带有一个名为 path 的 public 变量）但它没有任何进展。

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 变量，这样我就可以告诉它我在走什么路。我还创建了一个 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 class。

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's and second 的评论我设法想出了代码。

我修改如下（我只把相关部分放上去）

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

  [...]
  private int predecessor;

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

Graph.java 这里我创建了 calculatePath() 和 getPath() 方法。 calculatePath() 按照评论者的要求去做。 getPath() returns 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);
[...]

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

Dijkstra 的最短路径

Shortest Path with Dijkstra

java

dijkstra

shortest-path