Как ограничить кратчайший путь - алгоритм Дейкстры с максимальной стоимостью?

Question

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

Answer 1

Dijkstra - лучший поиск в первую очередь, то есть мы должны быть уверены, что расстояние до лучшего узла никогда не станет лучше. Это работает для минимума Дейкстры с неотрицательными ребрами. В общем случае вы можете использовать Ford-Bellman . Если вы хотите использовать не более n вершин, я могу предложить вам Динамическое программирование dp [vertex] [used_vertex_count] со сложностью O (| V | * n) состояний и памятью и O (| E | * n) временем. Или создайте матрицу смежности графа с нулями на главной диагонали и бесконечностью, вставленной в отсутствующий край, и вычислите ее показатель n a_ {ij} будет минимальным путем от i до j, используя не более n вершин.

Answer 2

Вы хотите использовать алгоритм Прима, потому что он находит все минимальное остовное дерево в данном графе.Тогда легко выбрать mst с желаемым ограничением.

Answer 3

Я думаю, что какой-то алгоритм, который включает в себя эвристику, будет лучше всего подходить здесь, поскольку эвристика представляет собой представление о том, «насколько близко» к цели вы находитесь на каждом шаге и какой узел приблизит вас к цели.Без этого, я думаю, что в худшем случае нам нужно будет запустить экспоненциальный алгоритм (который может быть, когда цель не может быть достигнута с использованием только n узлов. В этом случае мы рассмотрим все пути, которые используют n узлыпрежде чем сделать вывод, что проблема не может быть решена).

Один из примеров использования неэвристического алгоритма заключается в следующем: регулярно запускайте Дейкстры, выбирая узел с минимальным риском.По пути следите за количеством узлов, которые вы посетили.Если количество узлов превышает n, тогда откажитесь от текущего маршрута и вернитесь к предыдущему узлу и используйте узел со следующим наименьшим риском.Естественно, вы не можете вернуться на один уровень выше n, так как если бы цель была на следующем уровне, она была бы выбрана.Поэтому вы возвращаетесь к уровню n-2 и продолжаете.Это также будет экспоненциальным, поскольку не существует реального способа определить небытие без проверки всех путей.

Может быть, я что-то упустил.