Алгоритм Дейкстры с priority_queue

Question

Алгоритм Дейкстры с priority_queue

Я пытаюсь реализовать алгоритм Дейкстры. Я использую этот priority_queue

priority_queue<pair<PathInfo,string>,vector<pair<PathInfo,string> >,QueueComp> p;

где

class QueueComp{
PathComp* pc;
public:
QueueComp(PathComp*);
bool operator ()(const pair<PathInfo,string>&,const pair<PathInfo,string>& );
};

моя функция «Сравнить» Ошибка в том, что QueueComp не имеет конструктора по умолчанию и я запрещено создавать. Что я могу сделать, чтобы мой код компилировался? Кстати, это ошибка

error: no matching function for call to 'QueueComp::QueueComp()'

Это pathcomp.h

class PathComp{
public:
virtual bool betterThan(const PathInfo& path1,const PathInfo& path2)=0;
};

Это pathcomppl.h

#include "pathcomp.h"
class PathCompPL:public PathComp{
public:
virtual bool betterThan(const PathInfo& path1,const PathInfo& path2);
};

Это путь .comppl.cpp

#include "pathcomppl.h"
bool PathCompPL::betterThan(const PathInfo& path1,const PathInfo& path2){
if (path1.getTotalPrice()>path2.getTotalPrice())
return true;

if (path1.getTotalPrice()==path2.getTotalPrice() && path1.getTotalLength()>path2.getTotalLength())
return true;

return false;
}

Расширенное сообщение об ошибке

main.cpp: In constructor ‘std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = std::pair<PathInfo, std::basic_string<char> >; _Sequence = std::vector<std::pair<PathInfo, std::basic_string<char> > >; _Compare = QueueComp]’:
main.cpp:11:87: error: no matching function for call to ‘QueueComp::QueueComp()’
main.cpp:11:87: note: candidates are:
In file included from main.cpp:5:0:
queuecomp.h:14:5: note: QueueComp::QueueComp(PathComp*)
queuecomp.h:14:5: note:   candidate expects 1 argument, 0 provided
queuecomp.h:10:7: note: QueueComp::QueueComp(const QueueComp&)
queuecomp.h:10:7: note:   candidate expects 1 argument, 0 provided

1

c++dijkstra path-finding priority-queue

Решение

Другие решения

У вас нет конструктора по умолчанию, потому что вы должны инициализировать переменную с именем pc. У вас есть этот конструктор:

QueueComp(PathComp*);

Вы должны реализовать это так, чтобы pc ассоциировался с параметром.

Что касается вашего второго вопроса: первый элемент — это ваш следующий приоритет, второй элемент — это набор более низких приоритетов, а третий — сравнение очередей. Я надеюсь, это поможет вам.

0

Похоже, ваша проблема заключается в реализации правильного компаратора. Одна из альтернатив, которую вы могли бы рассмотреть, — создать компаратор, подобный следующему

struct CompareEdgeWeights : public binary_function<PathInfo*, PathInfo*, bool>
{
bool operator()(const PathInfo* left, const PathInfo* right) const
{
return left->getEdgeWeight() > right->getEdgeWeight();
}
}; // end struct

// Priority queue of node edges
priority_queue<PathInfo*,vector<PathInfo*>,CompareEdgeWeights > * edgePriorityQueue;

Имейте эту структуру, наследующую от binary_function и перегружайте оператор (). Затем вы можете использовать это в качестве компаратора для сортировки краев от минимального до максимального значения веса. Примечание: вам, возможно, придется немного подправить это, чтобы соответствовать вашей реализации. Трудно дать 100% правильное предложение, не видя больше вашей реализации.

0

Источник

Accepted Answer

Вам нужно инициализировать приоритетную очередь с дополнительным параметром, поскольку у вас есть конструктор не по умолчанию.

priority_queue<pair<PathInfo,string>,vector<pair<PathInfo,string> >,QueueComp> p(QueueComp(ptrToPathCompObject));

Дополнительный параметр (QueueComp(ptrToPathCompObject)) должен исправить вашу проблему.

Я предполагаю, что вы уже реализовали operator() в классе QueueComp.

2