Bellman-Ford с кучей не работает с пользовательской функцией сравнения

Я реализовал алгоритм Беллмана-Форда для решения задачи (с графом), но это решение было слишком медленным, поэтому я заменил очередь Беллмана-Форда кучей (std::set), поэтому решение для кратчайшего путь будет найден быстрее. (как-то близко алгоритм Дейкстры)

Теперь я вставляю номер узла в кучу, поэтому std::set по умолчанию будет сортировать узлы, используя их количество, а не их стоимость. Все нормально, и алгоритм дает правильные ответы.

Если я реализую пользовательскую функцию сравнения для std::set , чтобы узлы сортировались по их расстоянию, а не по их количеству, алгоритм больше не обеспечивает кратчайшее расстояние до остальных узлов.

Это моя функция сравнения:

 struct cmp{

    bool operator() (const int &a,const int &b) const{
        return (d[Q][a] < d[Q][b] );
    }
  };
 set <int,cmp> q;

Таким образом, будучи алгоритмом BF, алгоритм работает до тех пор, пока не станет возможным улучшение. Может ли функция сравнения каким-то образом «испортить» std::set, потому что это единственная причина, по которой я понимаю, почему добавление этой функции сравнения даст неверные ответы...

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


c++ graph dijkstra bellman-ford stdset
person XCS    schedule 12.02.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Насколько я помню, алгоритм Беллмана-Форда обновляет расстояние узел. Таким образом, использование веса в качестве ключа для std::set<T> не так просто: поиск в std::set<T> не найдет соответствующее значение, если вы просто измените расстояние. Что вам нужно сделать, чтобы следовать этому направлению, так это удалить узел, который нужно обновить, изменить расстояние узла и затем снова вставить его. Также обратите внимание, что объекты в std::set<T> должны иметь уникальный ключ: вставка уже существующего ключа не удастся.

Вы сказали, что используете std::set<int> как своего рода приоритетную очередь. Вы видели std::priority_queue<T>? Это делает именно это, но это более эффективно, чем использование std::set<T>. Проблема с std::priority_queue<T> в том, что вы не можете изменить приоритет объектов: у вас есть доступ только к текущей вершине. Давным-давно я создал набор приоритетных очередей (кучи), которые включали версии приоритетных очередей, позволяющие изменять приоритет объекта (они были частью исходных библиотек для Boost, но они так и не прошли процесс проверки). Я не знаю, как вы используете свою приоритетную очередь, и поэтому я не знаю, разумно ли смотреть на это направление.

Тем не менее, я не понимаю, почему вы все равно хотите std::set<T> для алгоритма Беллмана-Форда. Насколько я понимаю, алгоритм многократно проходит через граф и обновляет узлы с их новым кратчайшим расстоянием. Вы ознакомились с реализацией Boost алгоритм Беллмана-Форда?

person Dietmar Kühl    schedule 12.02.2012
comment
1) Я тоже это сделал (удаление и вставка), но безуспешно 2) Использование set вместо очереди заставит BF быстрее достичь решения, аналогично тому, как это делает алгоритм Дейкстры. 3) Я думаю, что алгоритм также должен работать, если я обновлю расстояния и НЕ обновлю набор, потому что даже если элементы больше не упорядочены, алгоритм все равно должен работать до достижения решения. - person XCS; 12.02.2012
comment
Я также забыл еще две вещи (добавлю их в ответ): std::set<int> хранит только одну копию каждого расстояния, т.е. если узлы в наборе будут иметь одинаковое расстояние, последние игнорируются. 2. Рассматривали ли вы возможность использования st::priority_queue<int> в качестве приоритетной очереди? - person Dietmar Kühl; 13.02.2012
comment
О, есть еще мультисет. Так что, даже если в наборе я храню уникальные числа, из-за функции сравнения узлы могут быть равны, поэтому требуется мультимножество... Это то, о чем я подумал перед сном :D Надеюсь, это сработает. - person XCS; 13.02.2012
comment
Хорошо, я решил проблему, используя мультисет. Но снова возникла другая проблема. Когда мне приходилось обновлять элемент (искать, удалять, вставлять), если было несколько элементов с одинаковым расстоянием, multiset.erase(multiset.find(element)) удалял элемент RANDOM из элементов с одинаковым расстоянием. Мне пришлось использовать equal_range и перебирать равные элементы в мультимножестве, чтобы найти именно тот узел, который я искал. - person XCS; 13.02.2012