Нахождение кратчайшего цикла в неориентированном графе, который включает 2 указанные вершины

Мне дан набор данных философов, который напоминает неориентированный граф. Философы хранятся в хэш-карте, где ключом является имя философа, а значением - список его соседей.

Пользователь дает 2 имени философа в качестве входных данных, и мне нужно найти кратчайший цикл (если таковой существует), который включает в себя этих 2 философов.

Сначала я подумал, что эта проблема очень похожа на проблему коммивояжера, однако в этой задаче у нас также есть расстояния перемещения, и каждую вершину можно посетить только один раз, что, похоже, здесь не так. Решение этой проблемы, кажется, связано с графиком, но я не совсем уверен, какой алгоритм использовать или даже какая проблема похожа на него.

Решение, которое я задумал, заключалось в нахождении всех циклов в данном графике, сводя результаты только к циклам, которые содержат философов, данных пользователем, и выбирая только самый короткий цикл из этих, так как я набрал бы количество циклов, основываясь на том, сколько «прыжков» «Они делают то, что по существу будет простой счетчик. Проблема в том, что я боюсь, что это не может быть оптимальным решением, учитывая, насколько большой набор данных и сколько циклов потенциально может быть сформировано (много).

Вывод должен быть в следующем формате: {u1, u2, u3, u4, u5, u1}, где u - имя каждого философа, который создает цикл, который я ищу. Если такого цикла не существует, то мне просто нужно напечатать соответствующее сообщение.

Всего 1 ответ


Вы можете использовать вариант алгоритма Suurballe. Как объясняет Википедия (на https://en.wikipedia.org/wiki/Suurballe's_algorithm ):

Алгоритм Суурбалла - это алгоритм нахождения двух непересекающихся путей в неотрицательно-взвешенном ориентированном графе, так что оба пути соединяют одну и ту же пару вершин и имеют минимальную общую длину. […] Основная идея алгоритма Суурбалла состоит в том, чтобы использовать алгоритм Дейкстры, чтобы найти один путь, изменить вес ребер графа, а затем запустить алгоритм Дейкстры во второй раз. Выходные данные алгоритма формируются путем объединения этих двух путей, отбрасывания ребер, которые пройдены в противоположных направлениях путями, и использования оставшихся ребер для формирования двух путей для возврата в качестве выходных данных.

и позже:

Версия алгоритма Suurballe, как описано выше, находит пути, которые имеют непересекающиеся ребра, но могут иметь общие вершины. Можно использовать тот же алгоритм, чтобы найти пути, не пересекающиеся с вершинами, заменив каждую вершину парой смежных вершин, одна со всеми входящими смежностями u-in исходной вершины, и одна со всеми исходящими смежностями u вне Два непересекающихся по ребру пути в этом модифицированном графе обязательно соответствуют двум непересекающимся по вершинам путям в исходном графе, и наоборот, поэтому применение алгоритма Суурбалла к модифицированному графу приводит к построению двух непересекающихся по вершинам путей в исходном графе.

Так что вам нужно будет перевести свой невзвешенный, неориентированный график | V | вершины и | E | невзвешенные ненаправленные ребра к взвешенному ориентированному графу 2 | V | вершины и 2 | E | + | V | взвешенные, направленные ребра; затем примените алгоритм Суурбалла; затем переведите результат обратно в цикл на исходном графике.


Есть идеи?

10000