Алгоритм Дейкста - список смежности и минимальная куча - Java

Question

Я использовал этот код для реализации ненаправленного графа и поиска кратчайшего пути от узла 0 до 5. Код печатает общее расстояние следующим образом:

Исходная вершина: расстояние от 0 до вершины 5:10

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

0 - 4 - 5.

Любое предложение, пожалуйста.Полный код приведен ниже:

    import java.util.LinkedList;

public class DijkstraUsingMinHeap {
    static class Edge {
        int source;
        int destination;
        int weight;

        public Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    static class HeapNode{
        int vertex;
        int distance;
    }
    static class Graph {
        int vertices;
        LinkedList<Edge>[] adjacencylist;

        Graph(int vertices) {
            this.vertices = vertices;
            adjacencylist = new LinkedList[vertices];
            //initialize adjacency lists for all the vertices
            for (int i = 0; i <vertices ; i++) {
                adjacencylist[i] = new LinkedList<>();
            }
        }

        public void addEdge(int source, int destination, int weight) {
            Edge edge = new Edge(source, destination, weight);
            adjacencylist[source].addFirst(edge);

            edge = new Edge(destination, source, weight);
            adjacencylist[destination].addFirst(edge); //for undirected graph
        }

        public void dijkstra_GetMinDistances(int sourceVertex){
            int INFINITY = Integer.MAX_VALUE;
            boolean[] SPT = new boolean[vertices];

//          //create heapNode for all the vertices
            HeapNode [] heapNodes = new HeapNode[vertices];
            for (int i = 0; i <vertices ; i++) {
                heapNodes[i] = new HeapNode();
                heapNodes[i].vertex = i;
                heapNodes[i].distance = INFINITY;
            }

            //decrease the distance for the first index
            heapNodes[sourceVertex].distance = 0;

            //add all the vertices to the MinHeap
            MinHeap minHeap = new MinHeap(vertices);
            for (int i = 0; i <vertices ; i++) {
                minHeap.insert(heapNodes[i]);
            }
            //while minHeap is not empty
            while(!minHeap.isEmpty()){
                //extract the min
                HeapNode extractedNode = minHeap.extractMin();

                //extracted vertex
                int extractedVertex = extractedNode.vertex;
                SPT[extractedVertex] = true;

                //iterate through all the adjacent vertices
                LinkedList<Edge> list = adjacencylist[extractedVertex];
                for (int i = 0; i <list.size() ; i++) {
                    Edge edge = list.get(i);
                    int destination = edge.destination;
                    //only if  destination vertex is not present in SPT
                    if(SPT[destination]==false ) {
                        ///check if distance needs an update or not
                        //means check total weight from source to vertex_V is less than
                        //the current distance value, if yes then update the distance
                        int newKey =  heapNodes[extractedVertex].distance + edge.weight ;
                        int currentKey = heapNodes[destination].distance;
                        if(currentKey>newKey){
                            decreaseKey(minHeap, newKey, destination);
                            heapNodes[destination].distance = newKey;
                        }
                    }
                }
            }
            //print SPT
            printDijkstra(heapNodes, sourceVertex);
        }

        public void decreaseKey(MinHeap minHeap, int newKey, int vertex){

            //get the index which distance's needs a decrease;
            int index = minHeap.indexes[vertex];

            //get the node and update its value
            HeapNode node = minHeap.mH[index];
            node.distance = newKey;
            minHeap.bubbleUp(index);
        }

        public void printDijkstra(HeapNode[] resultSet, int sourceVertex){
            for (int i = 0; i <vertices ; i++) {
                if ( i == 5 ) {
                System.out.println("Source Vertex: " + sourceVertex + " to vertex " +   + i +
                        " distance: " + resultSet[i].distance);}
            }
        }
    }
    static class MinHeap{
        int capacity;
        int currentSize;
        HeapNode[] mH;
        int [] indexes; //will be used to decrease the distance


        public MinHeap(int capacity) {
            this.capacity = capacity;
            mH = new HeapNode[capacity + 1];
            indexes = new int[capacity];
            mH[0] = new HeapNode();
            mH[0].distance = Integer.MIN_VALUE;
            mH[0].vertex=-1;
            currentSize = 0;
        }


        public void insert(HeapNode x) {
            currentSize++;
            int idx = currentSize;
            mH[idx] = x;
            indexes[x.vertex] = idx;
            bubbleUp(idx);
        }

        public void bubbleUp(int pos) {
            int parentIdx = pos/2;
            int currentIdx = pos;
            while (currentIdx > 0 && mH[parentIdx].distance > mH[currentIdx].distance) {
                HeapNode currentNode = mH[currentIdx];
                HeapNode parentNode = mH[parentIdx];

                //swap the positions
                indexes[currentNode.vertex] = parentIdx;
                indexes[parentNode.vertex] = currentIdx;
                swap(currentIdx,parentIdx);
                currentIdx = parentIdx;
                parentIdx = parentIdx/2;
            }
        }

        public HeapNode extractMin() {
            HeapNode min = mH[1];
            HeapNode lastNode = mH[currentSize];
//            update the indexes[] and move the last node to the top
            indexes[lastNode.vertex] = 1;
            mH[1] = lastNode;
            mH[currentSize] = null;
            sinkDown(1);
            currentSize--;
            return min;
        }

        public void sinkDown(int k) {
            int smallest = k;
            int leftChildIdx = 2 * k;
            int rightChildIdx = 2 * k+1;
            if (leftChildIdx < heapSize() && mH[smallest].distance > mH[leftChildIdx].distance) {
                smallest = leftChildIdx;
            }
            if (rightChildIdx < heapSize() && mH[smallest].distance > mH[rightChildIdx].distance) {
                smallest = rightChildIdx;
            }
            if (smallest != k) {

                HeapNode smallestNode = mH[smallest];
                HeapNode kNode = mH[k];

                //swap the positions
                indexes[smallestNode.vertex] = k;
                indexes[kNode.vertex] = smallest;
                swap(k, smallest);
                sinkDown(smallest);
            }
        }

        public void swap(int a, int b) {
            HeapNode temp = mH[a];
            mH[a] = mH[b];
            mH[b] = temp;
        }

        public boolean isEmpty() {
            return currentSize == 0;
        }

        public int heapSize(){
            return currentSize;
        }
    }
     public static void main(String[] args) {
            int vertices = 6;
            Graph graph = new Graph(vertices);
            int sourceVertex = 0;

            graph.addEdge(0, 1, 4);
            graph.addEdge(0, 2, 3);
            graph.addEdge(1, 3, 2);
            graph.addEdge(1, 2, 5);
            graph.addEdge(2, 3, 7);
            graph.addEdge(3, 4, 2);
            graph.addEdge(4, 0, 4);
            graph.addEdge(4, 1, 4);
            graph.addEdge(4, 5, 6);
            graph.dijkstra_GetMinDistances(sourceVertex);
    }
}

Заранее спасибо!

Answer 1

ОБНОВЛЕНИЕ: Изменено имя узлов и ребер, а также ребер списка.

Похоже, много кода для этого.Вот альтернативная реализация Java 8+.

Алгоритм Дейкстры полностью реализован в методе startAt.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public  final class Graph {
    private static final class Edge {
        final String name;
        final int weight;
        Edge(String name, int weight) {
            this.name = name;
            this.weight = weight;
        }
        @Override
        public String toString() {
            return this.name + ":" + this.weight;
        }
    }
    private static final class Node {
        final String name;
        Map<Node, Edge> edges = new HashMap<>();
        Node[] path;
        int pathWeight;
        Node(String name) {
            this.name = name;
        }
    }

    private Map<String, Node> nodes = new HashMap<>();

    public void addEdge(String sourceName, String destinationName, int weight, String edgeName) {
        Node source = this.nodes.computeIfAbsent(sourceName, Node::new);
        Node dest = this.nodes.computeIfAbsent(destinationName, Node::new);
        Edge edge = new Edge(edgeName, weight);
        source.edges.put(dest, edge);
        dest.edges.put(source, edge);
    }

    public void startAt(String startNodeName) {
        this.nodes.values().forEach(n -> n.path = null);
        Node source = this.nodes.computeIfAbsent(startNodeName, Node::new);
        source.path = new Node[] { source };
        source.pathWeight = 0;
        TreeSet<Node> pending = new TreeSet<>((a, b) -> Integer.compare(a.pathWeight, b.pathWeight));
        pending.add(source);
        while ((source = pending.pollFirst()) != null) {
            for (Entry<Node, Edge> edge : source.edges.entrySet()) {
                Node dest = edge.getKey();
                int weight = source.pathWeight + edge.getValue().weight;
                if (dest.path == null || weight < dest.pathWeight
                                      || (weight == dest.pathWeight && source.path.length + 1 < dest.path.length)) {
                    if (dest.path != null)
                        pending.remove(dest);
                    dest.path = Arrays.copyOf(source.path, source.path.length + 1);
                    dest.path[source.path.length] = dest;
                    dest.pathWeight = weight;
                    pending.add(dest);
                }
            }
        }
    }

    public String getPath(String endNodeName) {
        Node node = this.nodes.get(endNodeName);
        if (node == null || node.path == null)
            return "Unreachable";
        String path = Arrays.stream(node.path).map(n -> n.name).collect(Collectors.joining(" - "));
        String pathEdges = IntStream.range(1, node.path.length)
                .mapToObj(i -> node.path[i - 1].edges.get(node.path[i]).toString())
                .collect(Collectors.joining(" + "));
        return path + " (distance: " + node.pathWeight + " = " + pathEdges + ")";
    }
}

Тест 1 (исходные ребра))

Graph graph = new Graph();
graph.addEdge("0", "1", 4, "A");
graph.addEdge("0", "2", 3, "B");
graph.addEdge("1", "2", 1, "C");
graph.addEdge("1", "3", 2, "D");
graph.addEdge("2", "3", 4, "E");
graph.addEdge("3", "4", 2, "F");
graph.addEdge("4", "5", 6, "G");
graph.startAt("0");
System.out.println(graph.getPath("5"));

Выход 1

0 - 1 - 3 - 4 - 5 (distance: 14 = A:4 + D:2 + F:2 + G:6)

Тест 2 (обновленные ребра)

Graph graph = new Graph();
graph.addEdge("0", "1", 4, "A");
graph.addEdge("0", "2", 3, "B");
graph.addEdge("1", "3", 2, "C");
graph.addEdge("1", "2", 5, "D");
graph.addEdge("2", "3", 7, "E");
graph.addEdge("3", "4", 2, "F");
graph.addEdge("4", "0", 4, "G");
graph.addEdge("4", "1", 4, "H");
graph.addEdge("4", "5", 6, "I");
graph.startAt("0");
System.out.println(graph.getPath("5"));

Выход 2

0 - 4 - 5 (distance: 10 = G:4 + I:6)

См. IDEONE для демонстрации обоих тестов.