Некоторые соображения относительно графика:
У него есть начальная точка и конечная точка, он полностью связан, допускает циклы, и вес от A до b не обязательно равен вес от B до A. Он также может иметь отрицательные веса
О задаче:
Я хочу путь, который посещает больше узлов, и сумма весов CAN превышать указанную стоимость в середине, только конечный вес должен быть под границей стоимости. Разрешается проходить через один и тот же узел несколько раз.
То, что я пробовал:
Я изменил алгоритм Дейкстры, но возникающие бесконечные циклы делают задачу невозможной. Иногда, чтобы уменьшить вес, нужно несколько раз выполнить цикл, поэтому я должен разрешить повторное посещение узлов. Я даже не знаю, можно ли использовать Dijkstra в этой ситуации, так как поиск пути отличается от поиска самого длинного пути, но я много искал и не нашел al go, который удовлетворял бы моим потребностям. Я начинаю задаваться вопросом, возможно ли это ...
РЕДАКТИРОВАТЬ: я добавил новую функцию, которая позволяет пересмотреть узел без потери веса только N-факторных времен, где N - количество узлов. Это сработало, но решения сейчас требуют времени. Бесконечные циклы потери веса - это на самом деле хорошая вещь, и не о чем беспокоиться, поскольку в конечном итоге она будет настолько отрицательной, что сможет посещать все узлы, в лучшем случае.