-1

我正在尝试使用给定邻接矩阵的优先级队列来实现 Dijkstra 算法。我知道问题可能出在我将顶点添加到优先级队列中，但我不知道如何解决它！

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

此外，在您的算法中，您要删除顶部顶点两次，这是不合理的。算法应该是这样的：

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 回答