algorithm - 为什么在 Dijkstra 算法中使用堆？

Question

我为 Djkstra 算法编写了伪代码，以找到从源顶点到所有其他节点的最短路径。 我相信代码根本不需要最小堆。 共享的代码根本不使用堆。

如果我在这里做错了什么，有人可以告诉我吗？ 我的解决方案的时间复杂度是 O(V+E)。

请告诉我这是否有效以及我们能否从 djkstra 中消除堆。

提前致谢

我已经在一张纸上验证了它，但以防万一我错过了测试用例。

伪代码:--

q.add(src);

while (q is not empty) {
    int u = q.poll();

    if (visited[u] == true) {
        continue; //Node u has already served as a start vertex
    }

    for (Pair v: graph.getAdjacentsList()) {

        if (dist[u] + Pair.getweight() < dist[v]) {
            dist[v] = dist[u] + Pair.getweight();
            q.add(v.getDestinationVertex());
        }
        visited[u] = true; //Since we processed all children of u, mark it visited
    }

编辑1:对于每个邻居，用 min(已经注册的距离，dist(parent) + Weight(parent,child)) 更新他们的距离

Answer 1

假设如下图，并假设您没有使用某种最小堆:

假设 a 是我们的起始节点。您有可达的邻居 b 和 c。因为您不使用某种最小堆，所以您首先访问 b。现在有邻居 d，b 的成本为 1(总成本为 4，将为 d 设置)。您将 b 标记为已访问。

现在您访问 c 且邻居 b 可达。由于 2 的总成本低于 3，因此您将 b 的成本设置为 2，c 的成本为 1。您将 c 标记为已访问。

现在到达 d，它没有任何邻居，因此将其设置为已访问。

您确定的所有成本:

a -> c = 1,
a -> c -> b = 2,
a -> b -> d = 4,

但是经过c到d的最短路径是3。所以在这种情况下，算法没有找到最短的，而是任意路径，这不是Dijkstra算法的本意。使用某种最小堆，您会找到最短路径，因为您会在 b 之前访问 c。