java - 无向图的 Dijkstra 最短路径

Question

我的以下代码对于有向图运行得非常好，当给定无向图时，它不会返回最短路径。

public void Djikstra(int s){
    boolean[] marked = new boolean[V];
    dist = new double[V];

    for(int i = 0; i<V; i++){ # initializing array
        dist[i] = Double.POSITIVE_INFINITY;
    }
    dist[s] = 0.0;

    Queue<Integer> pqs = new PriorityQueue<Integer>();

    pqs.add(s);
    while(!pqs.isEmpty()){
        int v = pqs.poll();

        if(marked[v]) continue;
        marked[v] = true;

        for(Edge e : get_list(v)){ # get_list(v) will return an iterable from the adjacency list at index v 
            v = e.getV()
            int w = e.getW();
            if(dist[w] > dist[v] + e.getWeight()){
                dist[w] = dist[v] + e.getWeight();
                distances[w] = e #all the distances will be stored in this array
                pqs.add(w);
            }
        }
    }
}

我不确定我的错误是什么？我确信这是一个简单的错误，一些提示就可以完成任务。

谢谢。

编辑:

public void addEdge(Edge e){
    adj[e.getV()].add(e);
    adj[e.getW()].add(e);
}

Answer 1

考虑从节点 1 到 2 的有向路径与从节点 1 到 2 的无向路径之间的差异。

您需要向有向图(您的算法可以解决的)添加什么以使其等同于无向图？

编辑:

我想，已经明白了。提示如下:您当前正在 for 循环内更改重置 v 。这不会导致有向图出现错误，但是如果边被列为从 w 到 v 而不是 v 到 w 无向，会发生什么情况？

编辑2:

类似这样的事情:

首先，删除v = e.getV();

第二，将下一行更改为 int w = (v == e.getV()) ？ e.getW() : e.getV();

这会将 w 的值设置为边 v 不是的任何顶点。

第二个建议相当于以下内容(可能更容易阅读):

int w = e.getW();
if (w == v) {
    w = e.getV();
}