java - 无法使用 Dijkstra 算法找到最短路径？

Question

我正在尝试使用 Dijkstra 算法找到节点 a 和 z 之间的最短路径，但每次它都会给我错误的响应。

下面是我的代码-

public class DijkstraAlgorithm {

    // Am I mapping this correctly by looking at the below graph?
    // looks to me I got this wrong?
    private static final Graph.Edge[] GRAPH = { 
        new Graph.Edge("a", "g", 8), 
        new Graph.Edge("a", "b", 1), 
        new Graph.Edge("a", "e", 1), 
        new Graph.Edge("b", "c", 1), 
        new Graph.Edge("b", "e", 1),
        new Graph.Edge("b", "f", 2),
        new Graph.Edge("c", "g", 1),
        new Graph.Edge("c", "d", 1),
        new Graph.Edge("d", "f", 1),
        new Graph.Edge("d", "z", 1),
        new Graph.Edge("e", "f", 4),
        new Graph.Edge("f", "z", 4),
        new Graph.Edge("g", "z", 2),
    };

    private static final String START = "a";
    private static final String END = "z";

    public static void main(String[] args) {
        Graph g = new Graph(GRAPH);
        g.dijkstra(START);
        //  print the shortest path using Dijkstra algorithm
        g.printPath(END);
        //g.printAllPaths();
    }
}

class Graph {
    private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges

    /** One edge of the graph (only used by Graph constructor) */
    public static class Edge {
        public final String v1, v2;
        public final int dist;

        public Edge(String v1, String v2, int dist) {
            this.v1 = v1;
            this.v2 = v2;
            this.dist = dist;
        }
    }

    /** One vertex of the graph, complete with mappings to neighbouring vertices */
    public static class Vertex implements Comparable<Vertex> {
        public final String name;
        public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
        public Vertex previous = null;
        public final Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();

        public Vertex(String name) {
            this.name = name;
        }

        private void printPath() {
            if (this == this.previous) {
                System.out.printf("%s", this.name);
            } else if (this.previous == null) {
                System.out.printf("%s(unreached)", this.name);
            } else {
                this.previous.printPath();
                System.out.printf(" -> %s(%d)", this.name, this.dist);
            }
        }

        public int compareTo(Vertex other) {
            return Integer.compare(dist, other.dist);
        }
    }

    /** Builds a graph from a set of edges */
    public Graph(Edge[] edges) {
        graph = new HashMap<String, Vertex>(edges.length);

        //one pass to find all vertices
        for (Edge e : edges) {
            if (!graph.containsKey(e.v1))
                graph.put(e.v1, new Vertex(e.v1));
            if (!graph.containsKey(e.v2))
                graph.put(e.v2, new Vertex(e.v2));
        }

        //another pass to set neighbouring vertices
        for (Edge e : edges) {
            graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
            graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
        }
    }

    /** Runs dijkstra using a specified source vertex */
    public void dijkstra(String startName) {
        if (!graph.containsKey(startName)) {
            System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
            return;
        }
        final Vertex source = graph.get(startName);
        NavigableSet<Vertex> q = new TreeSet<Vertex>();

        // set-up vertices
        for (Vertex v : graph.values()) {
            v.previous = v == source ? source : null;
            v.dist = v == source ? 0 : Integer.MAX_VALUE;
            q.add(v);
        }

        dijkstra(q);
    }

    /** Implementation of dijkstra's algorithm using a binary heap. */
    private void dijkstra(final NavigableSet<Vertex> q) {
        Vertex u, v;
        while (!q.isEmpty()) {

            u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
            if (u.dist == Integer.MAX_VALUE)
                break; // we can ignore u (and any other remaining vertices) since they are unreachable

            //look at distances to each neighbour
            for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
                v = a.getKey(); //the neighbour in this iteration

                final int alternateDist = u.dist + a.getValue();
                if (alternateDist < v.dist) { // shorter path to neighbour found
                    q.remove(v);
                    v.dist = alternateDist;
                    v.previous = u;
                    q.add(v);
                }
            }
        }
    }

    /** Prints a path from the source to the specified vertex */
    public void printPath(String endName) {
        if (!graph.containsKey(endName)) {
            System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
            return;
        }

        graph.get(endName).printPath();
        System.out.println();
    }

    /** Prints the path from the source to every vertex (output order is not guaranteed) */
    public void printAllPaths() {
        for (Vertex v : graph.values()) {
            v.printPath();
            System.out.println();
        }
    }
}

根据计算，从节点 A 到节点 Z 的最短路径是 ABCDZ 但我得到 A -> E( 1) -> F(5) -> D(6) -> Z(7) 我上面的代码是错误的。

我想，通过查看图表，我在上述代码中对图表数据值的映射是错误的？有没有更好的方法来表示我的图表？

我上面的代码有什么问题吗？

Answer 1

问题是你的队列结构。它基于一个 TreeSet，它使用你的比较函数来排序。不幸的是，TreeSet 的每个键只能有一个值，因此如果两个元素比较相等(例如，所有具有 MAXINT 距离的顶点将比较相等)，它们实际上会被删除。

您可以通过打印出队列的长度来看到这一点，您插入了 8 个元素，但它的大小只能达到 2。

一个简单的解决方法是:

    public int compareTo(Vertex other) {
        if (dist==other.dist)
            return name.compareTo(other.name);
        return Integer.compare(dist, other.dist);
    }

这会阻止不同的顶点被视为相等。