Взвешенный график - найти все пути от X до y с максимальными остановками

Erick De Miranda Oliveira спросил: 13 июня 2018 в 02:45 в: java

Я работаю над проектом JAVA, который должен, между прочим, возвращать все возможные пути от x до y с max stops.Egg: каждый узел является городом, и каждый путь из одного города в другой имеет значения стоимости.

Я использую эту статью по ссылке, и вот те же модели, которые я использую. http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html

Он отлично работает, чтобы вернуть самый короткий путь от x до Y, но мне нужно ВСЕ возможные пути и затраты для каждого.

Кто-нибудь может мне помочь?

================================== ========================================== UPDATE

Например:

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

Входной график: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

Маршруты от C и заканчивающиеся на C максимум тремя остановками:

CDC (2 остановки) CEBC (3 остановки)

Маршруты от A и заканчивающиеся на C с максимальной остановкой 4 s:

ABC (2 остановки) ADC (2 остановки) AEBC (3 остановки) ADEBC (4 остановки)


2 ответа

Joseph D ответил: 13 июня 2018 в 03:35

Вес каждой из ссылок на узлы - это расстояние между ними.

i.e) A --- > 7 ---- > B --- > 3 --- > C --- > и т. д.

В этом случае общий вес этого пути от А до С будет суммой всех весов (расстояний) между каждой координатой.

Все возможные пути ниже максимума могут быть записаны с описанным выше описанием

Erick De Miranda Oliveira ответил: 13 июня 2018 в 04:07
Не понял. Я обновил вопрос для лучшего понимания.
Joseph D ответил: 13 июня 2018 в 04:17
Вам нужно расстояние между двумя точками вашего графика. A - (distanceFromAtoB) - B - (distanceFromBtoC) - C (2 остановки)
Executor1909 ответил: 15 июня 2018 в 07:15

Я бы использовал BFS вместо Dijkstra, если честно. Вы не ищете кратчайший путь, но любой путь. Таким образом, вы можете просто запустить BFS из узла x и после выполнения k шагов (я назову ваши максимальные шаги как k), вы можете остановить его. Каждый раз, когда он достигает y, вы можете добавить путь к вашему ответу.

Дополнительное видео по вопросу: Взвешенный график - найти все пути от X до y с максимальными остановками

Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm

3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method