0

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

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);
}
4

2 回答 2

2

考虑从节点 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();
}
于 2013-11-14T20:42:20.920 回答
0

您必须添加两个不同的边，即正边和逆边。改变

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

在

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

并且，当您添加边缘时，请这样做：

Edge e = new Edge(from, to, weight);
Edge f = new Edge(to, from, weight);

addEdge(e);
addEdge(f);
于 2016-06-28T08:13:20.320 回答