查找两个节点之间的最短距离

Question

我发现Dijkstra的算法并将其实现到我创建的图表中 - 它显示了我当地的地图代码工作正常，但我希望它显示它访问过的所有节点，以便从源节点到达位置Node。例如：如果我将源节点设置为1（Banstead），将位置节点设置为4（Whteleafe） - 我希望它可能将它访问的节点存储在数组中，如Array = {1，2，4}有什么想法吗？我想把它放在一个FXML文件上，并将节点作为椭圆并用线条连接它们 - 但为了做到这一点，我需要存储所访问节点的值。package dijkstras;public class Dijkstras {    static class createGraph{        int vertices;        int matrix[][];        public createGraph(int vertex){            this.vertices = vertex;            matrix = new int[vertex][vertex];        }        public void edge(int source, int destination, int weight){            matrix[source][destination] = weight;            matrix[destination][source] = weight;        }        int getMinVertex(boolean [] mst, int [] key){            int minKey = Integer.MAX_VALUE;            int vertex = -1;            for (int i = 1; i < vertices; i++) {                if(mst[i]==false && minKey>key[i]){                    minKey = key[i];                    vertex =i;                }            }            return vertex;          }        public void dijkstras(int sourceVertex){            boolean[] spt = new boolean[vertices];            int [] distance = new int[vertices];            int infinity = Integer.MAX_VALUE;            //setting all distances to infinity            for(int i=1; i<vertices; i++){                distance[i] = infinity;            }            //test for starting vertext = 1            distance[sourceVertex] = 1;            //create tree            for(int i=1; i<vertices; i++){

Answer 1

最简单的方法是跟踪每个节点的前身。到达结束节点后，您可以回溯以找出您来自哪里。

添加初始化

int [] comeFrom = new int[vertices];

改变

if(newKey<distance[vertexV])

    distance[vertexV] = newKey;

自

if(newKey<distance[vertexV]) {

    distance[vertexV] = newKey;

    comeFrom[vertexV] = vertexU;

}

以及打印输出时

List<Integer> path = new ArrayList();

int pos = LocationOfChosenUser;

while(pos != sourceVertex) {

   path.add(pos);

   pos = comeFrom[pos];

}

for (int i=path.size()-1; i>=0; i--) {

   System.out.print(path.get(i));

   if (i > 0) System.out.print(" -> ");

}

Answer 2

每次更新距离数组时，都需要跟踪到达节点的路径。这可以通过多种方式完成，我建议使用一个数组来存储为在距离数组中实现距离而采取的步骤。

distance[vertexV] = newKey;

lastStep[vertexV] = vertexU;

算法完成后，可以将路径从目标遍历回起点。基本上，你这样做：

int location = LocationOfChosenUser;

System.out.print(LocationOfChosenUser);

while (location != sourceVertex) {

    location = lastStep[LocationOfChosenUser];

    System.out.print(" <- " + location);

}

System.out.println();

此顺序为您提供相反的顺序（因此为箭头）。您将如何存储数字并将其反转留给您进行练习。<-