需要帮助理解 Dijkstra 算法

Question

我正在尝试遵循 Dijkstra 算法的伪代码，但我不明白它如何为我提供最短路径。按照这个伪代码：

DijkstrasAlgorithm(G, w, s)
    InitalizeSingleSource(G, s)
    S = 0
    Q = G.V
    while Q != 0
        u = ExtractMin(Q)
        S = S∪{u}
        for each vertex v ∈ G.Adj[u]
            Relax(u, v, w)

这是我最终得到的代码：

DijkstrasAlgorithm(string w, string s) {
    string u;
    string s;
    InitalizeSingleSource(s);
    for (map<string, Vertex*>::iterator it = vertices.begin(); 
    it!=vertices.end(); ++it) {
        minQ.insert(it->first, it->second->key);
    }
    while (u != "empty") {
        u = minQ.extractMin();
        if (!s.empty()) {
            s.append("->");
        }
        s.append(u);
        vector<Neighbor*>::iterator it = adjList[u].begin();
        while (it != adjList[u].end()) {
            relax(u, w, (*it)->weight);
            it++;
        }
    }
    return s;
}

问题是，这段代码没有给我最短路径。看看伪代码，我不明白它会怎样。如果我有 5 个顶点（a、b、c、d 和 e），假设我想找到从 a 到 c 的最短路径，这条最短路径是 a->b->c。所有这些代码都会给我 c->e->d->b->a.

我只是不明白这里的逻辑。我们使用 InitalizeSingleSource(s) 将顶点的所有键值初始化为 INT_MAX 除了 s，它是 0。从这里，我们找到顶点键值的最小值而不是使用 adjList.

我们不是在到达路径的尽头就停止，而是在 minQ 为空时停止。所有这一切都是打印所有顶点而不是最短路径。最重要的是，我们将大部分键设置为 INT_MAX，因此找到它们之间的最小值感觉都是多余的。

完成后，我们所有的松弛函数都与 G.E/G.Adj[u] 相关，即使我们在测量最小路径时没有使用边缘。

有很多对我来说没有意义，但我想最奇怪的部分是根据顶点 (G.V) 而不是边缘 (G.E).这应该如何找到最小路径？谁能解释我不理解的算法伪代码的哪一部分？谢谢！

编辑：也包括 "relax" 函数。

relax(string u, string v, int weight) {
    if (vertices[v]->key > (vertices[u]->key + weight)) { 
        vertices[v]->key = (vertices[u]->key + weight);
        vertices[v]->pi = new std::string(u);
    }
}

Answer 1

放松会降低 minQ 的值。

第一个提取的节点是源，因为 0 < MAX_INT。然后，每个相邻节点都会放松，这会将其 minQ 值减小到 0+c，其中 c 是从源到节点的边的成本，如果它低于当前的 minQ 值。这里是这样的，因为之前的值都是INT_MAX.

现在所有与源相邻的顶点都已标记有到达它们的已发现的最短路径。

那么其中一个处理过的顶点的minQ值最低，接下来会被提取处理。

您现在应该能够看到这个提取-> 松弛循环如何产生一个图表，其中每个节点都标有到达它的最低成本。

如果每次松弛发生时都更新指向松弛节点的指针，则可以从所需的目标节点向后走以读取最短路径。

需要帮助理解 Dijkstra 算法

Need help understanding Dijkstra's Algorithm

c++

dijkstra

data-structures