Блог

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

Я попытался использовать модифицированный алгоритм дейкстры для решения этой проблемы, сохранив в своей очереди приоритетов 3 кортежа. т.Е. (вес вершины, количество вершин на пути к этой вершине (включительно), индекс вершины). Мой алгоритм предотвращает попадание узлов, удаленных более чем на k вершин, в очередь приоритетов и, таким образом, рассмотрение по кратчайшему пути.

Каким-то образом мой алгоритм получает неправильный ответ. Одна из причин заключается в том, что если изначально меньшее взвешенное ребро приводит к недопустимому пути, а изначально большее взвешенное ребро приводит к допустимому пути, то мой алгоритм (будучи жадным) сообщит, что он не может найти допустимый путь к месту назначения.

Редактировать: Код решения отредактирован, поскольку это бесполезно.

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

(Ваш код будет легче читать, если вы создадите класс / структуру для некоторых вещей, которые вы храните в виде пар пар и т.д., Тогда вы сможете дать членам более четкие имена, чем second.first и т.д. Даже если вас устраивает текущее именование, дополнительная ясность может помочь вам получить некоторые другие ответы, если вышеупомянутое не помогло.)

Редактировать, чтобы ответить: «Как мне сохранить более дорогой путь, пока я не узнаю, что более дешевый путь приведет к решению?»

Ваша очередь приоритетов уже почти выполняет это — дело не в том, что каждая вершина (n) имеет полный путь, сохраненный, как я изначально подразумевал, в настоящее время вы просто сохраняете лучшую предыдущую вершину (n-1), которую можно использовать для перехода к вершине n, а также ее стоимость и количество вершин. Я говорю, что вместо сохранения этого одного наилучшего выбора для вершины n-1 вы сохраняете несколько вариантов, например, наилучший маршрут к A с использованием 3 предыдущих вершин — из вершины B и стоит 12, а наилучший маршрут с использованием 4 — из вершины C и стоит 10. (Во всех вышеперечисленных наилучших означает, что пока лучше всего найдено в поиске)

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

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

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

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