Кратчайший путь в ориентированном взвешенном графе, который использует не более k вершин

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

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

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

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

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

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

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

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