Алгоритм Дейкстры и смена источника в Java

Question

Итак, я пытаюсь реализовать алгоритм Дейкстры, чтобы найти кратчайший путь между двумя городами. Пока что мои классы:

Edge. java

package com.company;

public class Edge {

        private int weight;
        private Vertex startVertex;
        private Vertex targetVertex;

        public Edge(int weight, Vertex startVertex, Vertex targetVertex) {
            this.weight = weight;
            this.startVertex = startVertex;
            this.targetVertex = targetVertex;
        }

        public double getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public Vertex getStartVertex() {
            return startVertex;
        }

        public void setStartVertex(Vertex startVertex) {
            this.startVertex = startVertex;
        }

        public Vertex getTargetVertex() {
            return targetVertex;
        }

        public void setTargetVertex(Vertex targetVertex) {
            this.targetVertex = targetVertex;
        }
    }

, затем вершина. java

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Vertex implements Comparable<Vertex> {

    private String name;
    private List<Edge> adjacenciesList;
    private boolean visited;
    private Vertex predecessor;
    private double distance = Double.MAX_VALUE;

    public Vertex(String name) {
        this.name = name;
        this.adjacenciesList = new ArrayList<>();
    }

    public void addNeighbour(Edge edge) {
        this.adjacenciesList.add(edge);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public List<Edge> getAdjacenciesList() {
        return adjacenciesList;
    }

    public void setAdjacenciesList(List<Edge> adjacenciesList) {
        this.adjacenciesList = adjacenciesList;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public Vertex getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public double getDistance() {
        return distance;
    }

    public void setDistance(double distance) {
        this.distance = distance;
    }

    @Override
    public String toString() {
        return this.name;
    }

    @Override
    public int compareTo(Vertex otherVertex) {
        return Double.compare(this.distance, otherVertex.getDistance());
    }
}

и DijkstraShortestPath. java

    package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class DjikstraShortestPath {
        public void computeShortestPaths(Vertex sourceVertex){

            sourceVertex.setDistance(0);
            PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
            priorityQueue.add(sourceVertex);
            sourceVertex.setVisited(true);

            while( !priorityQueue.isEmpty() ){
                // Getting the minimum distance vertex from priority queue
                Vertex actualVertex = priorityQueue.poll();

                for(Edge edge : actualVertex.getAdjacenciesList()){

                    Vertex v = edge.getTargetVertex();
                    if(!v.isVisited())
                    {
                        double newDistance = actualVertex.getDistance() + edge.getWeight();

                        if( newDistance < v.getDistance() ){
                            priorityQueue.remove(v);
                            v.setDistance(newDistance);
                            v.setPredecessor(actualVertex);
                            priorityQueue.add(v);
                        }
                    }
                }
                actualVertex.setVisited(true);
            }
        }

        public List<Vertex> getShortestPathTo(Vertex targetVertex){
            List<Vertex> path = new ArrayList<>();

            for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
                path.add(vertex);
            }

            Collections.reverse(path);
            return path;
        }

    }

Теперь в Main я пытаюсь что-то вроде этого:

public static void main(String[] args) throws IOException {
{
int i, j;
 DjikstraShortestPath shortestPath = new DjikstraShortestPath();
        shortestPath.computeShortestPaths(vertex[0]); // setting the source to vertex[0]
        for(i=0; i<cities.size(); i++)
        {
            System.out.println("from"+vertex[0]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
            System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
        }
shortestPath.computeShortestPaths(vertex[1]); //changing the source
for(i=0; i<cities.size(); i++)
        {
            System.out.println("from"+vertex[1]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
            System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
        }
}

Проблема, с которой я сталкиваюсь, состоит в том, что вершина исходного источника (исходного города) [0] при установке производит правильный результат:

например:

from A to A the distance is 0.0 //A is the main source in this case vertex[0]
path: A

from A to F the distance is 13.5
path: A D C B F

Теперь, когда я переключаю источник на вершину [1]

from B to A the distance is 0.0 //wrong because it uses the data from the previous (vertex[0])
path: A //this is wrong too

from B to F the distance is 13.5
path: A D C B F //uses the previous info from vertex[0] even though the source is changed to vertex[1]

Попытался изменить функцию getShortestPathTo в функции DijkstraShortestPath. java к этому

public void getShortestPathTo(Vertex targetVertex){
            List<Vertex> path = new ArrayList<>();

            for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
                path.add(vertex);
            }
            Collections.reverse(path);
            for(int i = 0; i<path.size(); i++)
            {
                System.out.println(path.get(i).getName());
            }
            path.clear();

        }


    }

Сделал все вершины невидимыми, и теперь я столкнулся с проблемой «Недостаточно памяти». Есть проблема с кучей памяти, я буквально все перепробовал.

Любая помощь будет признательна.

Держите себя в безопасности и оставайтесь дома, люди!

Answer 1

Во время первого вызова computeShortestPaths вы записываете во все посещенные вершины, что они посещены, и их расстояние до источника.

Вы не сбрасываете эту информацию перед вызовом computeShortestPaths, поэтому вершины сохраняют свое расстояние и статус посещения (if(!v.isVisited()) гарантирует, что вы ничего не обновляете для узлов, которые уже были посещены при первом вызове).

Поэтому вам необходимо очистить всю информацию в объектах Vertex между два вызова или (лучше) рефакторинг вашего кода, чтобы эта информация сохранялась в объекте DjikstraShortestPath, а не в вершинах, и сбрасывалась при каждом вызове computeShortestPaths.

Answer 2

Я тоже сталкивался с той же проблемой (если я правильно отношусь к вашей) - все хорошо, пока вершина нашего происхождения не станет той вершиной, где мы можем достичь всех других вершин в ориентированном графе. Проблема начинается, когда мы выбрали исходную вершину, где мы не можем достичь всех других вершин в том же ориентированном графе. ex -

            2      4        1
        A---->B--------->C----->D
        | \              |  \   |
      7 |  \9          13|  3\  |6
        |   \            |    \ |
        v    v           v     vv
        E---->F--------->G----->H
          1      8         13

Выше, если мы выбрали вершину A, которая может достигать всех других вершин, т.е. B, C, D, E, FG & H - наш код в основном работает нормально. Но если мы выбрали вершину C, из которой мы можем добраться только до D, G & H выше. Проблема начнется, как когда мы извлечем Item для других недостижимых вершин B, C, E & F как минимальный элемент из нашего приоритета QUEUE, чтобы поместить их в окончательный набор / список кратчайших путей. Эти элементы будут иметь нереалистичное расстояние c в наборе / списке кратчайших путей, поскольку они не достижимы с C. Далее, когда мы проследим этот набор / список кратчайших путей для исходной вершины C в другие вершины, чтобы напечатать кратчайший путь, мы получим неверную информацию, поскольку недостижимые вершины также являются частью нашего окончательного набора / списка кратчайших путей.

Таким образом, решение состоит в том, чтобы ограничить запись элемента в окончательном наборе / списке, извлеченном из нашей очереди приоритетов, если этот элемент имеет нереалистичное расстояние c. Я проиллюстрировал этот код следующим образом -

Проверьте код в строке комментария ниже, который ограничивает любую недостижимую вершину, как если бы расстояние было нереальным c до нашего окончательного списка путей. // Ограничить доступ к элементам, имеющим нереалистичные значения c расстояния пути

package com.company.graph;

import java.util.*;

public class ShortestPath_Dijkstra {

    public static void main(String...args){

        String directedGraph =
                "\n\n            2      4        1\n" +
                "        A---->B--------->C----->D\n" +
                "        | \\              |  \\   |\n" +
                "      7 |  \\9          13|  3\\  |6\n" +
                "        |   \\            |    \\ |\n" +
                "        v    v           v     vv\n" +
                "        E---->F--------->G----->H\n" +
                "          1      8         13" ;



        // We store number instated of letters since in real world every vertex may have full qualified name ex - "LasVegas" instead of just "A"
        Map<Integer,String> vertices = new HashMap<>();
        vertices.put(0,"A");
        vertices.put(1,"B");
        vertices.put(2,"C");
        vertices.put(3,"D");
        vertices.put(4,"E");
        vertices.put(5,"F");
        vertices.put(6,"G");
        vertices.put(7,"H");

        Map<Edge, Integer> edges = new HashMap<>();

        //Implemented edges as a Map where for each entry -  key is a vertex and value is List containing edges i.e. all connecting vertices along with the weight !!
        Map<Integer, List<Edge>> verticesEdges = new HashMap<>();
        verticesEdges.put(0, new LinkedList<>(List.of(new Edge(1,2), new Edge(4,7),new Edge(5,9) )));
        verticesEdges.put(1, new LinkedList<>(List.of(new Edge(2,4))));
        verticesEdges.put(2, new LinkedList<>(List.of(new Edge(3,1),new Edge(6,13), new Edge(7,3))));
        verticesEdges.put(3, new LinkedList<>(List.of(new Edge(7,6))));
        verticesEdges.put(4, new LinkedList<>(List.of(new Edge(5,1) )));
        verticesEdges.put(5, new LinkedList<>(List.of(new Edge(6,8) )));
        verticesEdges.put(6, new LinkedList<>(List.of(new Edge(7,13))));
        verticesEdges.put(7, new LinkedList<>());


        Integer origin = 2; // alias C

        Map<Integer, Item> pathMap = getShortestPathMap(origin, vertices, verticesEdges);

        displayShortestPaths(directedGraph, origin, pathMap, vertices);

    }



    //Dijkstra function
    static Map<Integer, Item> getShortestPathMap(Integer origin, Map<Integer,String> vertices, Map<Integer, List<Edge>> verticesEdges){

        Map<Integer, Item> pathMap = new HashMap<>();

        PriorityQueue<Item> queue = new PriorityQueue<>();
        //Initialization of queue.
        vertices.keySet().forEach(v -> {
            if(v.equals(origin)){
                queue.add(new Item(v, 0, null));
            }else {
                queue.add(new Item(v));
            }
        });

        while(!queue.isEmpty()){

            Item currItem = queue.poll();

            //Restrict entry of Items having unrealistic path distances
            if(currItem.getDistance() != Integer.MAX_VALUE && currItem.getDistance() >= 0){
                pathMap.put(currItem.vertex, currItem);
            }

            verticesEdges.get(currItem.getVertex()).forEach(edge -> {
                //Get item in queue corresponding to vertex of this edge
                Item connItem = new Item(edge.getV());
                Iterator<Item> iterator = queue.iterator();
                boolean found = false;
                while(iterator.hasNext()){
                    Item inQueue = iterator.next();
                    if(inQueue.equals(connItem)){
                        connItem = inQueue;
                        found = true;
                        break;
                    }
                }
                //Update this connection Item distance if more than sum distance of current vertex and connecting edge weight. And also parent as current vertex.
                if(found && connItem.getDistance() > currItem.getDistance() + edge.getW()){
                    queue.remove(connItem);
                    queue.add(new Item(connItem.getVertex(), currItem.getDistance() + edge.getW(), currItem.getVertex()));
                }
            });
        }

        return pathMap;
    }

    //Display  function
    static void displayShortestPaths(String directedGraph, Integer origin,  Map<Integer, Item> pathMap, Map<Integer,String> vertices){

        System.out.println("For a directed Graph - " +  directedGraph );
        System.out.format("%nShortest Paths to all vertices starting from %S - %n", vertices.get(origin));

        vertices.keySet().forEach(v ->{
            if(pathMap.get(v)!=null){
                System.out.format("%n Shortest path(distance) from %S --> %S is %S", vertices.get(origin), vertices.get(v), pathMap.get(v).getDistance());
                System.out.format(" via vertices : ");

                Stack<String> path = new Stack<>();
                path.push(vertices.get(v));
                while(pathMap.get(v).getParent() != null){
                    v = pathMap.get(v).getParent();
                    path.push(vertices.get(v));
                }
                System.out.format("%S", path.pop());
                while (!path.empty()){
                    System.out.format("-->%S", path.pop());
                }
            }
        });
    }


    // Below class are Data Structures to store and process graph
    static class Edge {

        Integer v;   //Connecting Vertex
        Integer w;   //weight Of edge

        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
        int getV() { return v; }
        int getW() { return w; }
    }


    static class Item implements Comparable<Item>{

        Integer vertex;
        Integer distance = Integer.MAX_VALUE;
        Integer parent = null;

        Item(Integer vertex) {
            this.vertex = vertex;
        }

        Item(Integer vertex, Integer distance, Integer parent) {
            this.vertex = vertex;
            this.distance = distance;
            this.parent = parent;
        }

        Integer getVertex() { return vertex; }
        Integer getDistance() { return distance; }

        Integer getParent() { return parent; }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Item item = (Item) o;
            return vertex.equals(item.vertex);
        }

        @Override
        public int hashCode() {
            return Objects.hash(vertex);
        }

        @Override
        public int compareTo(Item item) {
            return this.distance - item.distance;
        }
    }

}

Давайте запустим приведенный выше код, я полагаю, чтобы увидеть только кратчайшие расстояния до достижимых вершин из C не любые нереалистичные c (недостижимые) -

For a directed Graph - 

            2      4        1
        A---->B--------->C----->D
        | \              |  \   |
      7 |  \9          13|  3\  |6
        |   \            |    \ |
        v    v           v     vv
        E---->F--------->G----->H
          1      8         13

Shortest Paths to all vertices starting from C - 

 Shortest path(distance) from C --> C is 0 via vertices : C
 Shortest path(distance) from C --> D is 1 via vertices : C-->D
 Shortest path(distance) from C --> G is 13 via vertices : C-->G
 Shortest path(distance) from C --> H is 3 via vertices : C-->H
Process finished with exit code 0

Давайте также проверим, что «если условие» для ограничения нереалистичных c записей не оказало негативного влияния на случай, когда вершина A является исходной (т. е. все остальные вершины в графе достижимы) - для этого нам нужно сделать 1 замену строки, чтобы сказать, что исходная вершина теперь A,

Integer origin = 0; // alias A

For a directed Graph - 

            2      4        1
        A---->B--------->C----->D
        | \              |  \   |
      7 |  \9          13|  3\  |6
        |   \            |    \ |
        v    v           v     vv
        E---->F--------->G----->H
          1      8         13

Shortest Paths to all vertices starting from A - 

 Shortest path(distance) from A --> A is 0 via vertices : A
 Shortest path(distance) from A --> B is 2 via vertices : A-->B
 Shortest path(distance) from A --> C is 6 via vertices : A-->B-->C
 Shortest path(distance) from A --> D is 7 via vertices : A-->B-->C-->D
 Shortest path(distance) from A --> E is 7 via vertices : A-->E
 Shortest path(distance) from A --> F is 8 via vertices : A-->E-->F
 Shortest path(distance) from A --> G is 16 via vertices : A-->E-->F-->G
 Shortest path(distance) from A --> H is 9 via vertices : A-->B-->C-->H
Process finished with exit code 0

Answer 3

Вам нужно инициализировать все ваши расстояния до бесконечности в начале алгоритма. distance, сохраняемый в каждой вершине, является «кратчайшим расстоянием, видимым до сих пор», поэтому, если вы оставите расстояние А в 0 от первого прогона вашего алгоритма, второй прогон будет предполагать, что существует более короткий путь к А и он имеет длину 0. Аналогично для visited.

См. также шаги 1 и 2 описания алгоритма в Википедии :

1. Отметьте все узлы как непосещенные. [...]
2. Назначьте каждому узлу предварительное значение расстояния: установите его равным нулю для нашего начального узла и равным бесконечности для всех других узлов, [...]

Работает первый раз, потому что distance инициализируется на Double.MAX_VALUE и visited на false. Поэтому перед повторным запуском алгоритма вам необходимо сбросить:

for(i=0; i<vertex.size; i++)
{
    vertex[i].setDistance(Double.MAX_VALUE);
    vertex[i].setVisited(false);
}