Я использую библиотеку JGraphT для работы с довольно сложной топологией. Библиотека предоставляет множество библиотечных алгоритмов, таких как «Кратчайший путь Дейкстры». Мой вопрос: мне нужен способ найти путь через какую-то выделенную вершину, которая не является «самой короткой» и даже может показаться «противоречащей интуиции» для выбора (хотя есть гарантированный путь от начала до конца через этот вершина в графе). Например, предположим, я могу добраться из Нью-Йорка в Париж напрямую, но я хочу поехать в Париж, отправившись сначала в Сидней, затем в Токио, затем в Москву, затем в Берлин, а затем в Париж. Итак, моя цель - Париж, но я хочу определить некоторые конкретные «промежуточные» вершины, которые ДОЛЖНЫ БЫТЬ на пути. Какие есть средства для достижения этого с помощью JGrapthT?
JGraphT - библиотечный алгоритм для поиска пути через определенную вершину
comment
Вот уже отвеченный вопрос, касающийся аналогичной проблемы (не относящейся конкретно к JGraphT, а к теории графов в целом): stackoverflow.com/questions/222413/ Как ни странно, я искал решения раньше задавая вопрос, но не нашел его, возможно, из-за ключевого слова JGraphT, которое я включил.
- person Vivit schedule 28.04.2020
Ответы (1)
Это очень интересный вопрос. Я не знаю конкретного решения, но я бы просто нашел кратчайший путь между каждым набором желаемых узлов.
Так ты найдешь кратчайший путь для
Paris -> Sydney
Sydney -> Tokyo
Tokyo -> Moscow
Moscow -> Berlin
Berlin -> Paris
а затем сложите их вместе.
Конечно, это может означать, что вы в любом случае пройдете через один из желаемых узлов. Я не знаю, как бы вы хотели поступить в этой ситуации.
person
mwarren
schedule
28.04.2020
Сомневаюсь, что получится лучше, чем это: /
- person Moritz Groß; 02.06.2020
