2

ウィキペディアのページの疑似コードからダイクストラのアルゴリズムを実装しようとしました。キューがポーリングされた後に、現在のノードがターゲット ノードであるかどうかをテストする条件を設定しました。その場合、アルゴリズムは a から b へのパスを中断して戻すことになります。

Adjacency Matrix の範囲内のすべてのノードが実際に存在することがわかっているため、この条件は常に満たされます。プログラムは、ロンドン地下鉄マップの接続をモデル化することです。

とにかく、私はしばらくの間これを理解しようとしてきましたが、これまでのところ私にはわかりません. 多分誰かが問題を見つけることができます。ああ、adj私のグラフの隣接行列です。

    /**
   Implementation of Dijkstra's Algorithm taken from "Introduction to 
   Algorithms" by Cormen, Leiserson, Rivest and Stein. Third edition.

   d = Array of all distances.
   pi = Previous vertices.
   S = Set of vertices whose final shortest path weights have been
   determined.
   Q = Priority queue of vertices.
**/
public ArrayList<Integer> dijkstra(Integer a, Integer b){
    final double[] d = new double[adj.length];
    int[] pi = new int[adj.length];
    HashSet<Integer> S = new HashSet<Integer>();
    PriorityQueue<Integer> Q = new PriorityQueue<Integer>(d.length, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                Double dblA = d[a-1];
                Double dblB = d[b-1];
                return dblA.compareTo(dblB);
            }
        });

    for(int i=0; i<d.length; i++){
        d[i] = Double.POSITIVE_INFINITY;
    }
    d[a] = 0f;
    for(int i=0; i<d.length; i++){
        Q.add(i+1);
    }

    while(Q.size() > 0){
        int u = Q.poll();
        if(u == b){
            System.out.println("jjd");
            ArrayList<Integer> path = new ArrayList<Integer>();
            for(int i=pi.length-1; i>=0; i--){
                path.add(pi[i]);
            }
            return path;
        }
        S.add(u);

        if(d[u] == Double.POSITIVE_INFINITY){
            break;
        }

        for(int v=0; v<adj.length; v++){
            double tmp = d[u] + adj[u][v];
            if(tmp < d[v]){
                d[v] = tmp;
                pi[v] = u;
            }
        }
    }
    return new ArrayList<Integer>();
}

}

編集:- デバッグを行った後、while ループの本体が 1 回だけ実行されているようです。

4

2 に答える 2

2 
    if(d[u] == Double.POSITIVE_INFINITY){
        break;
    }

    for(int v=0; v<adj.length; v++){
        double tmp = d[u] + adj[u][v];
        if(tmp < d[v]){
            d[v] = tmp;
            pi[v] = u;
        }
    }

ループ本体の値を変更してdも優先キューは再配置されないため、最初のノードをポップした後にたまたまキューの先頭にあった要素がその隣接要素の 1 つである場合を除き、d[u] == Double.POSITIVE_INFINITY次の反復でそれから休憩。

ダイクストラのアルゴリズムでは、ノードの距離が変化したときにキューが更新されることが重要です。java.util.PriorityQueue<E>はその機能を提供していないため、それを使用することは自明ではありません。更新のたびに更新されたノードを削除して再度追加する以外に使用する方法はありません。もちろん、これはあまり効率的ではありませんO(size)。

非効率性は、すべてのノードをキューに入れないようにすることで軽減できます。最初のノードのみを追加してスターを付け、ループ内でまだ見られていないネイバーのみを挿入し、既にキューにあるネイバーを削除して再挿入します。これにより、キューが短くなり、平均して削除が安くなります.

O(log size)効率的な実装のためには、優先度のより高速な ( ?) 更新を可能にするカスタム優先度キューが必要です。

于 2012-11-19T22:18:54.493 に答える
0

System.out.println からプログラムを実行したときにコンソールに「jjd」が出力された場合、問題は次のようになります。

         if(u == b){
            System.out.println("jjd");
            ArrayList<Integer> path = new ArrayList<Integer>();
            for(int i=pi.length-1; i>=0; i--){
                path.add(pi[i]);
            }
            return path;

「リターンパス」を呼び出しているとき。実際にはメソッド全体を壊して「パス」を返します。

于 2012-11-19T22:03:59.470 に答える