带邻接表无向图的 Dijkstra 算法

Question

我正在尝试编写一种方法，使用 Dijkstra 算法找到从一个顶点到另一个顶点的最短路径长度。但它没有给出正确的输出。您能否就问题出在哪里提供一些建议？

unsigned distDIJKSTRA(unsigned vert1, unsigned vert2)
    {
        vector<Vertex3*> pq;
        Vertex3* v;
        unsigned distance = UINT_MAX;
        for (unsigned i = 0; i < vertices.size(); i++)
        {
            if (vertices[i]->value == vert1)
                v = new Vertex3(vertices[i], 0);
            else 
                v = new Vertex3(vertices[i], distance);
            pq.push_back(v);
        }

        make_heap(pq.begin(), pq.end(), lowerPrior);
        unsigned newDist;
        while (!pq.empty())
        {
            Vertex3* currV = pq.front();

            // If the destination is reached
            if (currV->vert->value == vert2)
                return currV->dist;

            pop_heap(pq.begin(), pq.end(), lowerPrior);
            pq.pop_back();

            // Checking if the route through currV is shorter
            for (unsigned i = 0; i < currV->vert->adjList.size(); i++)
            {
                Vertex3* nextV = nullptr;
                for (unsigned j = 0; j < pq.size(); j++)
                    if (pq[j]->vert == currV->vert->adjList[i]) {
                        nextV = pq[j];
                        break;
                    }
                if (nextV != nullptr)
                {
                    newDist = currV->dist + getWeight(currV->vert, nextV->vert);
                    if (newDist < nextV->dist)
                        nextV->dist = newDist;
                }
                else
                    continue;
            }
            sort_heap(pq.begin(), pq.end(), lowerPrior);    
        }
        return UINT_MAX;
    }

Answer 1

更新距离后，您的向量将不再是堆。此外，调用 sort_heap 本身也会丢弃堆属性，而不是修复它。（参见 http://en.cppreference.com/w/cpp/algorithm/sort_heap）请改为调用 make_heap。

另请注意内存泄漏：您永远不会释放为 Vertex3 对象分配的内存。

带邻接表无向图的 Dijkstra 算法

Dijkstra algorithm with Adjacency list Undirected Graph

c++

dijkstra