-1

隣接行列が与えられた優先キューを使用してダイクストラアルゴリズムを実装しようとしています。問題はおそらく優先キューに頂点を追加するところにあることはわかっていますが、それを修正する方法がわかりません。

static int dijkstra(int[][] g, int i, int j) {
    // Get the number of vertices in G
    int n = g.length;
    int counter = 0;

    PriorityQueue<Vertex> q = new PriorityQueue<Vertex>(n, new Comparator<Vertex>() {       
        public int compare(Vertex a, Vertex b) {
            Vertex v1 = (Vertex) a;
            Vertex v2 = (Vertex) b;
            if (v1.getD() > v2.getD()) {
                return 1;
            } else if (v1.getD() < v2.getD()) {
                return -1;
            } else {
                return 0;
            }
        }
    });
    int[] distance = new int[n];
    for (int l = 0; l < n; l++) {
        distance[l] = 99999;
    }
    distance[i] = 0;

    for (int l = 0; l < n/2; l++) {
        for (int m = 0; m < n; m++) {
            if (g[l][m] > 1) {
                System.out.printf("%d was added \n", g[l][m]);
                q.add(new Vertex(l, g[l][m]));
            }
        }
    }
    while (!q.isEmpty()) {
        int u = 0;
        for (int z = 0; z < n; z++) {
            if (distance[z] < distance[u]) {
                u = z;
            }
        }
        if (distance[u] == 99999) { break; }
        q.remove();
        for (int l = 0; l < n; l++) {
            if (g[u][l] > 1) {
                int alt = distance[u] + g[u][l];
                if (alt < distance[l]) {
                    distance[l] = alt;
                    q.remove();
                    q.add(new Vertex(u, distance[l]));
                }
            }
        }
    }

    for (int k = 0; k < n; k++) {
        System.out.printf("==>%d", distance[j]);
    }
    return distance[j];
}

と：

class Vertex {
    int v,d;
    public Vertex(int num, int dis) {
        v = num;
        d = dis;
    }
    public int getV() {
        return v;
    }
    public int getD() {
        return d;
    }
}

私は次のマトリックスでテストしています：

 0  0  0  0  0  0  0 38  0  0  0  0  0  0  0  0
 0  0  0  0 65  0 64  0  6  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  6  8  0  0  0 62
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0 65  0  0  0  0  0  0  0  6  0  0  0  0 55  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0 64  0  0  0  0  0 53  0  0 36  0 45  0  0  0
38  0  0  0  0  0 53  0  0  0  0 91  0 29  0  0
 0  6  0  0  0  0  0  0  0  0  0 95 55  0  0  0
 0  0  0  0  6  0  0  0  0  0  0  0  0  0  0  0
 0  0  6  0  0  0 36  0  0  0  0  0  0  0  0  0
 0  0  8  0  0  0  0 91 95  0  0  0 60  0  0  0
 0  0  0  0  0  0 45  0 55  0  0 60  0  0  0  0
 0  0  0  0  0  0  0 29  0  0  0  0  0  0  0  0
 0  0  0  0 55  0  0  0  0  0  0  0  0  0  0  0
 0  0 62  0  0  0  0  0  0  0  0  0  0  0  0  0

そして、開始は0、終了はn - 1です。取得する必要がありますが195、距離は変更されていないようです！

4

1 に答える 1

1

距離を印刷するときは、イテレータであるj間は常に配列を印刷します。k距離は一定に見えますが、変化しています。

for (int k = 0; k < n; k++) {
    System.out.printf("==>%d", distance[k]);
}

また、アルゴリズムでは、最上位の頂点を2回削除していますが、これはもっともらしいことではありません。代わりに、アルゴリズムは次のようになります。

while (!q.isEmpty()) {
    int u = q.peek().v;
    q.remove();
    for (int l = 0; l < n; l++) {
        if (g[u][l] > 1) {
            int alt = distance[u] + g[u][l];
            if (alt < distance[l]) {
                distance[l] = alt;
                q.add(new Vertex(u, distance[l]));
            }
        }
    }
}
于 2012-12-02T14:44:24.873 に答える