使用最小堆实现Dijkstra算法失败

Question

我尝试使用Java中的最小堆来实现Dijkstra算法，但每次都得到错误的输出。我在这里找到了相同主题的C++代码。下面是我的图表，绿色节点 A 是源节点，红色节点 F 是目标节点。我的目标是找出从 A 到 F 的最短路径长度。

以下是我的代码：

public class Dijkstra {
    private static Heap heap = new Heap();
    private static int[][] graph;

    public Dijkstra() {
        graph = new int[6][6];
        /*
         * The graph value assignment is just for checking the code. node A is
         * referred as node 0, node B is referred as node 1 and so on. finally
         * node F is referred as node 5.
         */
        graph[0][0] = graph[0][1] = graph[0][3] = graph[0][4] = graph[0][5] = graph[1][0] = graph[1][1] = graph[1][4] = graph[1][5] = graph[2][2] = graph[2][5] = graph[3][0] = graph[3][3] = graph[4][0] = graph[4][1] = graph[4][4] = graph[5][0] = graph[5][1] = graph[5][2] = graph[5][5] = 0;
        graph[1][2] = graph[2][1] = graph[2][3] = graph[3][2] = graph[3][4] = graph[4][3] = graph[4][5] = graph[5][4] = 1;
        graph[1][3] = graph[3][1] = 3;
        graph[0][2] = graph[2][0] = 4;
        graph[2][4] = graph[4][2] = 5;
        graph[3][5] = graph[5][3] = 8;
    }

    public static void main(String[] args) {
        Dijkstra dij = new Dijkstra();
        // Source is node A (node 0) and destination is node F (node 5)
        System.out.println(dij.solve(6, 0, 5));
    }

    public int solve(int numOfNodes, int source, int dest) {
        heap.push(source, 0);
        while (!heap.isEmpty()) {
            int u = heap.pop();
            if (u == dest)
                return heap.cost[dest];
            for (int i = 0; i < numOfNodes; i++) {
                if (graph[u][i] >= 0)
                    heap.push(i, heap.cost[u] + graph[u][i]);
            }
        }
        return -1;
    }
}

class Heap {
    private int[] data;
    private int[] index;
    public int[] cost;
    private int size;

    public Heap() {
        data = new int[6];
        index = new int[6];
        cost = new int[6];

        for (int i = 0; i < 6; i++) {
            index[i] = -1;
            cost[i] = -1;
        }

        size = 0;
    }

    public boolean isEmpty() {
        return (size == 0);
    }

    private void shiftUp(int i) {
        int j;
        while (i > 0) {
            j = (i - 1) / 2;
            if (cost[data[i]] < cost[data[j]]) {
                // swap here
                int temp = index[data[i]];
                index[data[i]] = index[data[j]];
                index[data[j]] = temp;
                // swap here
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i = j;
            } else
                break;
        }
    }

    private void shiftDown(int i) {
        int j, k;
        while (2 * i + 1 < size) {
            j = 2 * i + 1;
            k = j + 1;
            if (k < size && cost[data[k]] < cost[data[j]]
                    && cost[data[k]] < cost[data[i]]) {
                // swap here
                int temp = index[data[k]];
                index[data[k]] = index[data[i]];
                index[data[i]] = temp;
                // swap here
                temp = data[k];
                data[k] = data[i];
                data[i] = temp;

                i = k;
            } else if (cost[data[j]] < cost[data[i]]) {
                // swap here
                int temp = index[data[j]];
                index[data[j]] = index[data[i]];
                index[data[i]] = temp;
                // swap here
                temp = data[j];
                data[j] = data[i];
                data[i] = temp;

                i = j;
            } else
                break;
        }
    }

    public int pop() {
        int res = data[0];
        data[0] = data[size - 1];
        index[data[0]] = 0;
        size--;
        shiftDown(0);
        return res;
    }

    public void push(int x, int c) {
        if (index[x] == -1) {
            cost[x] = c;
            data[size] = x;
            index[x] = size;
            size++;
            shiftUp(index[x]);
        } else {
            if (c < cost[x]) {
                cost[x] = c;
                shiftUp(index[x]);
                shiftDown(index[x]);
            }
        }
    }
}

在运行整个代码时，我得到的输出是0，但是可以清楚地看出从节点A到节点F的成本为7（4 + 1 + 1 + 1 = A-C-D-E-F）。错误在哪里？

- ravi

---

你可以删掉 line graph[0][0] = graph[0][1] = ... 这一行，因为它们默认是0。 - Artem Oboturov

你已经将许多边设置为零权重，因此最短路径为0。如果你将这些边设置为-1，那么你的“if (graph[u][i] >= 0)”语句将正确捕获它们。 - Running Wild

此外，当您弹出一个节点时，需要检查您是否已经评估过它，否则可能永远无法终止。 - Running Wild

@RunningWild：先生，您能否再解释一下？我该如何检查已弹出的元素是否已经被评估过？ - ravi

@RaviJoshi：保持一个布尔数组，大小与图中节点数量相同，初始值均为false。当你弹出一个节点时，首先检查该数组中的布尔值是否为true，如果是，则弹出下一个元素，否则将其布尔值标记为true，以便下次不再评估它。 - Running Wild

Answer 1

您可以使用graph[u][i] >= 0来测试是否存在边。但是，您定义的图中零值表示没有边，因此应该将其更改为

if (graph[u][i] > 0) ...

solve方法内部。另一个可能性是在矩阵中用-1标记不存在的边。这样也可以允许成本为零的边。

- Howard

---

是的，完全正确。现在正常工作。'heap'类中有三个整数数组。是否可能进一步减少heap代码？ - ravi

Answer 2

在堆中，你有两个值： 一个标识节点的索引， 一个标识节点距离的成本。 你弹出成本，也就是距离，但你却像使用索引来标识节点一样使用它。

public int pop() {
        int res = data[0];
        ...
        return res;
    }

在solve()函数中：

  int u = heap.pop();
  if (u == dest)
  ...

- azzurroverde