Нахождение кратчайшего расстояния между двумя узлами

Question

Я нашел и внедрил алгоритм Дейкстры в созданный мной график, который показывает карту моей местности

Код работает нормально, но я хочу, чтобы он отображал все узлы, которые он посетил, чтобы добраться до узла местоположения от исходного узла. Так, например: если я установлю исходный узел в 1 (Banstead), а узел местоположения в 4 (Whteleafe) - я хочу, чтобы он, возможно, сохранял в массиве узлы, которые он посещал, например Array = {1,2,4} Any идеи? Я хочу поместить это в файл 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++){

                int vertexU = getMinVertex(spt, distance);

                spt[vertexU] = true;   
                //go through all possible paths adjacent to vertex
                for(int vertexV=1; vertexV<vertices; vertexV++){
                    //check if edge between Vu and Vv exists
                    if(matrix[vertexU][vertexV]>0){

                        //checks vertexV exists and if distance is not infinite
                        if(spt[vertexV]==false && matrix[vertexU][vertexV]!=infinity){

                            int newKey = matrix[vertexU][vertexV] + distance[vertexU];
                            if(newKey<distance[vertexV])
                                distance[vertexV] = newKey;
                        }
                    }
                }
            }

            System.out.println();      
            printDijkstras(sourceVertex, distance);
        }

        public void printDijkstras(int sourceVertex, int [] key){
            System.out.println("Dijkstra Algorithm:");
            int LocationOfChosenUser = 10;  
            System.out.println("Source Vertex: "+ sourceVertex + " to " +
              LocationOfChosenUser + " distance: " + (key[LocationOfChosenUser]-1));
        }
    }

    public static void graph() {
       int vertices = 18;
       createGraph graph = new createGraph(vertices);
       int sourceVertex = 8;
       //adding all nodes
       graph.edge(1,2,4);   graph.edge(1,17,3); 
       graph.edge(2,1,4);   graph.edge(2,4,4);   graph.edge(2,10,5); 
       graph.edge(3,4,1);   graph.edge(3,6,5);   graph.edge(3,5,2);
       graph.edge(4,2,4);   graph.edge(4,3,1);   graph.edge(4,5,2); 
       graph.edge(5,4,2);   graph.edge(5,3,2);   graph.edge(5,6,3);  graph.edge(5,9,4);  graph.edge(5,10,5); 
       graph.edge(6,3,5);   graph.edge(6,5,3);   graph.edge(6,7,2);  graph.edge(6,9,2);
       graph.edge(7,6,2);   graph.edge(7,8,5);   
       graph.edge(8,7,5);   graph.edge(8,9,4);   graph.edge(8,12,5);
       graph.edge(9,5,4);   graph.edge(9,8,4);   graph.edge(9,11,5); graph.edge(9,6,2); 
       graph.edge(10,2,5);  graph.edge(10,5,5);  graph.edge(10,13,1);graph.edge(10,14,3); graph.edge(10,17,6);
       graph.edge(11,9,5);  graph.edge(11,12,3); graph.edge(11,13,3);
       graph.edge(12,8,5);  graph.edge(12,11,3); graph.edge(12,15,4);
       graph.edge(13,11,3); graph.edge(13,10,1); graph.edge(13,14,2);
       graph.edge(14,10,3); graph.edge(14,13,2); graph.edge(14,16,6); graph.edge(14,15,6);
       graph.edge(15,12,4); graph.edge(15,14,5); graph.edge(15,16,9); 
       graph.edge(16,15,9); graph.edge(16,17,1); graph.edge(16,14,6);
       graph.edge(17,1,3);  graph.edge(17,16,1);

       graph.dijkstras(sourceVertex);
    }
    public static void main(String[] args){
        graph();
    }
}

Как вы можете видеть, я установил sourceVertex на 8, а LocationVertex (LocationOfChosenUser) на 10. и результат выглядит примерно так:

 Dijkstra Algorithm:
Source Vertex: 8 to 10 distance: 12

Answer 1

Каждый раз, когда вы обновляете массив расстояний, вам нужно отслеживать, какой путь был выбран для достижения узла. Это можно сделать несколькими способами, и я рекомендую массив, в котором хранится информация о том, какой шаг был сделан для достижения расстояния в массиве расстояний.

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();

Этот порядок дает вам обратный порядок (следовательно, стрелка <-). Как вы храните числа и переворачиваете их, оставлено для вас в качестве упражнения.

Answer 2

Самый простой способ сделать это - просто отслеживать предшественников каждого узла.Когда вы достигли конечного узла, вы можете вернуться, чтобы выяснить, откуда вы пришли.

Добавить инициализацию

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(" -> ");
}