Dijksta 算法 - 邻接表和最小堆 - 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;

            }

Answer 1

更新：更改为名称节点和边，并列出边。似乎有很多代码。这是一个替代的 Java 8+ 实现。Dijkstra 算法完全在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&nbsp; final class Graph {&nbsp; &nbsp; private static final class Edge {&nbsp; &nbsp; &nbsp; &nbsp; final String name;&nbsp; &nbsp; &nbsp; &nbsp; final int weight;&nbsp; &nbsp; &nbsp; &nbsp; Edge(String name, int weight) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.name = name;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.weight = weight;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public String toString() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return this.name + ":" + this.weight;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private static final class Node {&nbsp; &nbsp; &nbsp; &nbsp; final String name;&nbsp; &nbsp; &nbsp; &nbsp; Map<Node, Edge> edges = new HashMap<>();&nbsp; &nbsp; &nbsp; &nbsp; Node[] path;&nbsp; &nbsp; &nbsp; &nbsp; int pathWeight;&nbsp; &nbsp; &nbsp; &nbsp; Node(String name) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.name = name;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private Map<String, Node> nodes = new HashMap<>();&nbsp; &nbsp; public void addEdge(String sourceName, String destinationName, int weight, String edgeName) {&nbsp; &nbsp; &nbsp; &nbsp; Node source = this.nodes.computeIfAbsent(sourceName, Node::new);&nbsp; &nbsp; &nbsp; &nbsp; Node dest = this.nodes.computeIfAbsent(destinationName, Node::new);&nbsp; &nbsp; &nbsp; &nbsp; Edge edge = new Edge(edgeName, weight);&nbsp; &nbsp; &nbsp; &nbsp; source.edges.put(dest, edge);&nbsp; &nbsp; &nbsp; &nbsp; dest.edges.put(source, edge);&nbsp; &nbsp; }&nbsp; &nbsp; public void startAt(String startNodeName) {&nbsp; &nbsp; &nbsp; &nbsp; this.nodes.values().forEach(n -> n.path = null);&nbsp; &nbsp; &nbsp; &nbsp; Node source = this.nodes.computeIfAbsent(startNodeName, Node::new);&nbsp; &nbsp; &nbsp; &nbsp; source.path = new Node[] { source };&nbsp; &nbsp; &nbsp; &nbsp; source.pathWeight = 0;&nbsp; &nbsp; &nbsp; &nbsp; TreeSet<Node> pending = new TreeSet<>((a, b) -> Integer.compare(a.pathWeight, b.pathWeight));&nbsp; &nbsp; &nbsp; &nbsp; pending.add(source);&nbsp; &nbsp; &nbsp; &nbsp; while ((source = pending.pollFirst()) != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Entry<Node, Edge> edge : source.edges.entrySet()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node dest = edge.getKey();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int weight = source.pathWeight + edge.getValue().weight;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (dest.path == null || weight < dest.pathWeight&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; || (weight == dest.pathWeight && source.path.length + 1 < dest.path.length)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (dest.path != null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pending.remove(dest);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dest.path = Arrays.copyOf(source.path, source.path.length + 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dest.path[source.path.length] = dest;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dest.pathWeight = weight;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pending.add(dest);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public String getPath(String endNodeName) {&nbsp; &nbsp; &nbsp; &nbsp; Node node = this.nodes.get(endNodeName);&nbsp; &nbsp; &nbsp; &nbsp; if (node == null || node.path == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return "Unreachable";&nbsp; &nbsp; &nbsp; &nbsp; String path = Arrays.stream(node.path).map(n -> n.name).collect(Collectors.joining(" - "));&nbsp; &nbsp; &nbsp; &nbsp; String pathEdges = IntStream.range(1, node.path.length)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .mapToObj(i -> node.path[i - 1].edges.get(node.path[i]).toString())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .collect(Collectors.joining(" + "));&nbsp; &nbsp; &nbsp; &nbsp; return path + " (distance: " + node.pathWeight + " = " + pathEdges + ")";&nbsp; &nbsp; }}测试 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"));输出 10 - 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"));输出 20 - 4 - 5 (distance: 10 = G:4 + I:6)有关这两个测试的演示，请参阅IDEONE。