JGraphT - библиотечный алгоритм для поиска пути по некоторой заданной c вершине

Question

Я использую библиотеку JGraphT для работы с довольно сложной топологией. Библиотека предоставляет множество библиотечных алгоритмов, таких как Dijkstra Shortest Path. Мой вопрос: мне нужен способ найти путь через какую-то выделенную вершину, которая не является «самой короткой» и даже может показаться «нелогичной» для выбора (даже несмотря на то, что через этот путь существует гарантированный путь от начала до конца). вершина в графе). Например, предположим, я могу добраться из Нью-Йорка в Париж напрямую, но я хочу go в Париж, отправившись сначала в Сидни, затем в Токио, затем в Москву, затем в Берлин, затем в Париж. Так что Париж - моя цель, но я хочу определить некоторые специфические c «промежуточные» вершины, которые ДОЛЖНЫ БЫТЬ на пути. Какие есть средства для достижения этой цели с помощью JGrapthT?

Answer 1

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

Итак, вы найдете кратчайший путь для

Paris -> Sydney
Sydney -> Tokyo
Tokyo -> Moscow
Moscow -> Berlin
Berlin -> Paris

и затем сложите их вместе.

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