为什么我在 Java 中为无向图实现的 Dijkstra 算法不起作用？

Question

我的有向图实现工作正常。这是一个 "lazy" 版本，因为它使用简单的优先级队列而不是索引队列。我更改了代码以获得无向图的解决方案，但它不起作用。 dijkstra(int s)是classGraph的一个方法。 Graph 的实现基于邻接列表。整个代码基于Sedgewick的书的解释。

public void dijkstra(int s) {

    marked = new boolean[V];
    distTo = new int[V];
    edgeTo = new Edge[V];

    Comparator<Edge> comparator = new Comparator<Edge>() {

        public int compare(Edge e1, Edge e2) {

            int dist1 = distTo[e1.either()] + e1.weight();
            int dist2 = distTo[e2.either()] + e2.weight();

            if (dist1 < dist2) {
                return -1;
            } else if (dist1 > dist2) {
                return 1;
            } else {
                return  0;
            }
        }
    };

    pq = new PriorityQueue<Edge>(comparator);

    for (int v = 0; v < V; ++v) {
        distTo[v] = Integer.MAX_VALUE;
    }

    distTo[s] = 0;

    relax(s);

    while (!pq.isEmpty()) {

        Edge e = pq.poll();

        int v = e.either();
        int w = e.other(v);

        if (!marked[w]) {
            relax(w);
        }
    }
}

private void relax(int v) {

    marked[v] = true;

    for (Edge e : adj[v]) {

        int w = e.other(v);

        if (distTo[w] > distTo[v] + e.weight()) {

            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            pq.add(e);
        }
    }
}

Answer 1

我解决了。愚蠢的错误。而不是添加边

v->w and w->v

我添加了边

v->w and w->w

即我添加了两次相同的边缘，但没有创建反向边缘。

为什么我在 Java 中为无向图实现的 Dijkstra 算法不起作用？

Why my Dijkstra's algorithm implementation in Java for undirected graph doesn't work?

java

algorithm

graph

dijkstra

undirected-graph