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  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。