C ++ при использовании приоритетной очереди Отладочное утверждение не выполнено, выражение: недопустимая куча

Question

Среда:
- Win7 pro x64
- VS2010
- C ++
- Пустой проект

Цель: реализация алгоритма кратчайшего пути Дейкстры с использованием очереди приоритетов.

Проблема: при запуске программы возникает ошибка «Отладка», выражение: недопустимая ошибка кучи.Если пользователь вводит исходную вершину как 1, все работает нормально.Утверждение происходит только тогда, когда исходная вершина отлична от 1. Кроме того, если утверждения игнорируются, код в конце концов завершается и выводит правильные пути через граф.Я предполагаю, что ошибка связана с изменением данных, на которые указывают указатели в очереди приоритетов, но если это так, я не понимаю, почему использование 1 в качестве источника позволяет коду успешно завершаться.

Спасибо за любую помощь!

header:

#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

Возможно, вы нажимаете Vertex экземпляров с infinite расстояниями.Сравнение двух infinite расстояний не дало бы ни одно из них на меньше , чем другое, и, следовательно, аннулирует ваш компаратор.

Если это строго учебное упражнение и вам действительно не требуется double расстояния, я предлагаю вам использовать целые расстояния и использовать «большое» число вместо infinite.

Используя N битовые целые числа, было бы неплохо использовать 2^(N-3) в качестве infiniteзначение, потому что добавление их приведет к 2^(N-2), который все еще может быть представлен целым числом со знаком N бит (не так 2^(N-1)), и это большее значение, чем простой infinite, то есть infinite + infinite > infinite, который сохраняет ваш порядоквменяемый.

Answer 2

Вы должны вытолкнуть верхний элемент из priority_queue сразу после вашего вызова q.top (). Вместо этого вы делаете q.pop () после помещения нового элемента в очередь с помощью q.push(it->first);

Мне кажется, что это не то, что вы хотите, потому что теперь вы потенциально можете вытолкнуть элемент, отличный от того, который вы считали верхним элементом.

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 (), очередь понимает, что находится в недопустимом состоянии и выдает сообщение