C++使用优先级队列时调试断言失败，表达式：无效堆

Question

环境：
- Win7 专业版 x64
- VS2010
- C++
- 空项目

目标： 使用优先级队列实现 Dijkstra 的最短路径算法。

问题： 当程序运行时，它会收到“调试断言失败，表达式：无效堆”错误。如果用户输入源顶点为 1，则一切正常。仅当源顶点不为 1 时才会发生断言。此外，如果忽略断言，代码最终会完成并输出通过图形的正确路径。我猜测该错误与更改优先级队列中的指针指向的数据有关，但如果是这种情况，我不明白为什么使用 1 作为源可以让代码成功完成。

感谢您的任何帮助！

标题：

#ifndef _GRAPH_H_
#define _GRAPH_H_
#include <map>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

class Graph
{

public:

    struct Vertex
    {
        int name; // V number
        double dv; // distance
        Vertex* pv; // previous V* from this V
        map<Vertex*, double> neighbors; // map of all neighbors/distances connected to vert
    };

    vector<Vertex*> verts; // vector of all V*

    void dijkstra(ifstream& stream, int start_vert); // create graph & find shortest paths
    void printPath(Vertex* v); // echo path

    class CompareVert // overloaded compare operator for priorty queue data struct, sort queue so V with smallest dist on top
    {
    public:
        bool operator()(const Vertex* v1, const Vertex* v2) const
        {
            return v1->dv > v2->dv;
        }
    };
};

#endif

实现：

#include "Graph.h"
#include <iostream>
#include <queue>
#include <limits> // used for numeric_limits<double>::infinity()
#include <vector>

using namespace std;

int path_length = 0;

void Graph::printPath(Vertex* v) // print shortest paths
{
    if (v->pv != NULL)
    {
        printPath(v->pv);
        cout << " -> ";
    }
    cout << v->name;
}

void Graph::dijkstra(ifstream& stream, int start_vert) // create graph & get shortest path
{
    /////////////////////////////////////////////
    /////////////// create graph ////////////////
    /////////////////////////////////////////////

    int total_edges;
    priority_queue<Vertex*, vector<Vertex*>, CompareVert> q;
    double infinity = numeric_limits<double>::infinity();
    int source;
    int dest;
    double dist;
    stream >> total_edges;
    for (int i=0;i<total_edges;i++)
    {
        stream >> source;
        stream >> dest;
        stream >> dist;
        bool source_exists = false;
        bool dest_exists = false;
        Vertex* _source;
        Vertex* _dest;

        for (int i=0;i<verts.size();i++)
        {
            if (verts.at(i)->name == source) // vertex already exists, set to V
            {
                _source = verts.at(i);
                source_exists = true;
                break;
            }
        }

        for (int i=0;i<verts.size();i++)
        {
            if (verts.at(i)->name == dest) // vertex already exists, set to V
            {
                _dest = verts.at(i);
                dest_exists = true;
                break;
            }
        }

        if (!source_exists) // create vert
        {
            _source = new Vertex;
            _source->name = source;
            _source->dv = infinity;
            _source->pv = NULL;
            verts.push_back(_source);
        }

        if (!dest_exists) // create vert
        {
            _dest = new Vertex;
            _dest->name = dest;
            _dest->dv = infinity;
            _dest->pv = NULL;
            verts.push_back(_dest);
        }
        _source->neighbors.insert(pair<Vertex*, double>(_dest, dist)); // populate V's adjacency map
    }

    for (int i=0;i<verts.size();i++)
    {
        if (verts.at(i)->name == start_vert) // set source
        {
            verts.at(i)->dv = 0;
        }       
        q.push(verts.at(i)); // push all vertices to priority queue
    }

    /////////////////////////////////////////////
    ////////////////  find paths  ///////////////
    /////////////////////////////////////////////

    vector<int> displayed;
    bool print; // flag to call printPath
    while (!q.empty())
    {
        map<Vertex*, double>::iterator it;
        Vertex* temp = q.top(); // get V with smallest dist
        print = true;
        for (it = temp->neighbors.begin(); it!=temp->neighbors.end();++it)
        {
            if ((temp->dv + it->second) < it->first->dv)
            {
                print = false;
                it->first->dv = (temp->dv + it->second);
                it->first->pv = temp;
                q.push(it->first);
            }
        }

        for (int i=0;i<displayed.size();i++) // if end V of path has already been printed, do not print
        {
            if (displayed.at(i) == temp->name)
                print = false;
        }

        if (print == true)
        {
            printPath(temp);
            path_length = temp->dv;
            cout << " total distance = " << path_length <<endl << endl;
            displayed.push_back(temp->name);
        }

        path_length = 0;
        q.pop();
    }
}

驱动程序：

#include "Graph.h"
#include <stdio.h>
#include <iostream>
#include <string>
#include <fstream>
#include <list>

using namespace std;

string fname;
int vname;
string line;

int main(void)
{
    cout << "Please enter the file to read in a graph (graph.txt): ";
    cin >> fname;
    cout << "Please choose a starting vertex (1 is a good choice): ";
    cin >> vname;
    cout << endl;

    ifstream my_stream (fname);
    Graph my_graph;
    my_graph.dijkstra(my_stream, vname);
    my_stream.close();
}

graph.txt：

12
1 2 2
1 4 1
2 4 3
2 5 10
3 1 4
3 6 5
4 3 2
4 5 2
4 6 8
4 7 4
5 7 6
7 6 1

Answer 1

您应该在调用 q.top() 之后立即从priority_queue 中弹出顶部元素。相反，您在使用 q.push(it->first); 将新元素推入队列后执行 q.pop()

在我看来这不是您想要的，因为您现在可能会这样做弹出一个与您认为的顶部元素不同的元素。

Answer 2

您可能正在将 Vertex 实例推送到无限 距离。比较两个无限距离不会产生任何一个比另一个小，因此使您的比较器无效。

如果这严格来说是一个学习练习，并且您并不真正需要双距离，我建议您使用整数距离并使用“大”数字代替无限。

使用 N 位整数时，最好使用 2^(N-3) 作为您的 无限 值，因为将它们相加会产生 < code>2^(N-2) 仍然可以用有符号的 N 位整数表示（不是这样 2^(N-1)），并且它是一个比简单的无限，即无限 + 无限 >无限，这使您的排序保持理智。

Answer 3

您应该避免修改优先级队列中当前的元素，至少不要以修改其优先级的方式。
顶点的优先级由CompareVert给出，它取决于dv的值。
在“查找路径部分”中，

 if ((temp->dv + it->second) < it->first->dv)
 {
     print = false;
     it->first->dv = (temp->dv + it->second);   // <-- here is the problem!
     it->first->pv = temp;
     q.push(it->first);
  }

对 dv 的分配会影响队列中当前的元素。当您调用 q.push() 时，队列意识到它处于无效状态并抱怨