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 のリセットを変更しています。これは有向グラフではエラーを引き起こしませんが、エッジが無向 v から w ではなく w から v に移動するとリストされている場合はどうなりますか?

EDIT2：

このようなもの：

まず、削除しますv = e.getV();

次に、次の行を次のように変更しますint w = (v == e.getV()) ? e.getW() : e.getV();

これにより、w の値が、エッジ v ではない頂点に設定されます。

この 2 番目の提案は、次のものと同等です (少し読みやすいかもしれません)。

int w = e.getW();
if (w == v) {
    w = e.getV();
}
于 2013-11-14T20:42:20.920 に答える
0

直接と逆の 2 つの異なるエッジを追加する必要があります。変化する

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 に答える