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

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])&nbsp; &nbsp; distance[vertexV] = newKey;自if(newKey<distance[vertexV]) {&nbsp; &nbsp; distance[vertexV] = newKey;&nbsp; &nbsp; comeFrom[vertexV] = vertexU;}以及打印输出时List<Integer> path = new ArrayList();int pos = LocationOfChosenUser;while(pos != sourceVertex) {&nbsp; &nbsp;path.add(pos);&nbsp; &nbsp;pos = comeFrom[pos];}for (int i=path.size()-1; i>=0; i--) {&nbsp; &nbsp;System.out.print(path.get(i));&nbsp; &nbsp;if (i > 0) System.out.print(" -> ");}

Answer 2

每次更新距离数组时，都需要跟踪到达节点的路径。这可以通过多种方式完成，我建议使用一个数组来存储为在距离数组中实现距离而采取的步骤。distance[vertexV] = newKey;lastStep[vertexV] = vertexU;算法完成后，可以将路径从目标遍历回起点。基本上，你这样做：int location = LocationOfChosenUser;System.out.print(LocationOfChosenUser);while (location != sourceVertex) {&nbsp; &nbsp; location = lastStep[LocationOfChosenUser];&nbsp; &nbsp; System.out.print(" <- " + location);}System.out.println();此顺序为您提供相反的顺序（因此为箭头）。您将如何存储数字并将其反转留给您进行练习。<-