Алгоритм графа для нахождения всех связей между двумя произвольными вершинами

Question

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

У меня есть набор записей. Для этого набора записей у меня есть данные подключения, которые указывают, как пары записей из этого набора соединяются друг с другом. В основном это представляет собой неориентированный граф, записи которого представляют собой вершины, а данные соединения - ребра.

Все записи в наборе имеют информацию о соединении (т. Е. Нет записей о потерях; каждая запись в наборе соединяется с одной или несколькими другими записями в наборе).

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

Примечание: две выбранные записи всегда будут разными (то есть начальная и конечная вершины никогда не будут одинаковыми; циклов нет).

Например:

    If I have the following records:
        A, B, C, D, E

    and the following represents the connections: 
        (A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
        (C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

        [where (A,B) means record A connects to record B]

Если бы я выбрал B в качестве моей начальной записи и E в качестве моей конечной записи, я бы хотел найти все простые пути через соединения с записями, которые соединяли бы запись B с записью E.

   All paths connecting B to E:
      B->E
      B->F->E
      B->F->C->E
      B->A->C->E
      B->A->C->F->E

Это пример, на практике у меня могут быть наборы, содержащие сотни тысяч записей.

Answer 1

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

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

вы начинаете с одной записи в очереди, которая имеет начальный узел и пустой путь.

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

Теперь вы можете использовать нечто подобное, но когда вы найдете решение, вместо того, чтобы остановиться, добавьте это решение в свой «найденный список» и продолжайте.

Вам необходимо отслеживать список посещенных узлов, чтобы вы никогда не возвращались к себе, иначе у вас будет бесконечный цикл.

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

Answer 2

В дополнение к ответу Кейси Уотсона, есть еще одна реализация Java. Инициализация посещенного узла начальным узлом.

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }

Answer 3

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

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

Затем поиск возвращается, возвращаясь к самому последнему узлу, который он еще не завершил.

Я недавно написал в блоге на эту тему, опубликовав пример реализации C ++.

Answer 4

Я нашел способ перечислить все пути, включая бесконечные, содержащие циклы.

http://blog.vjeux.com/2009/project/project-shortest-path.html

Поиск атомных путей и циклов

Definition

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

Первое определение атомного пути, которое я принял, - это путь, который не проходит через один и тот же узел дважды. Однако я узнал, что это не все возможности. После некоторого размышления я понял, что узлы не важны, как бы то ни было ребра! Так что атомный путь - это путь, который не проходит через одно и то же ребро дважды.

Это определение удобно, оно также работает для циклов: атомный цикл в точке A - это атомный путь, который идет из точки A и заканчивается в точке A.

Осуществление

Atomic Paths A -> B

Чтобы получить весь путь, начиная с точки А, мы собираемся рекурсивно пройти по графику из точки А. При прохождении дочернего объекта мы собираемся сделать ссылку дочерний -> родительский, чтобы узнать все края мы уже пересекли. Прежде чем перейти к этому дочернему элементу, мы должны пройти по этому связанному списку и убедиться, что указанное ребро еще не прошло.

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

Freeing the list

Проблема возникает, когда вы хотите освободить связанный список. Это в основном дерево в цепочке в обратном порядке. Решением будет двойная связь этого списка, и когда все атомные пути будут найдены, освободите дерево от начальной точки.

Но разумным решением является использование подсчета ссылок (по мотивам Сборщика мусора). Каждый раз, когда вы добавляете ссылку на родителя, вы добавляете ее к счетчику ссылок. Затем, когда вы достигаете конца пути, вы возвращаетесь назад и освобождаетесь, пока счетчик ссылок равен 1. Если он выше, вы просто удаляете один и останавливаетесь.

Atomic Cycle A

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

Как вы видели ранее, весь граф просматривается при поиске атомного пути. Вместо этого мы можем ограничить область поиска до сильно связанного компонента, содержащего A. Для нахождения этих компонентов требуется простой обход графа с помощью алгоритма Тарьяна.

Объединение атомных путей и циклов

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

Answer 5

Насколько я могу судить, решения Райана Фокса ( 58343 , Кристиана ( 58444 ) и вас ( 58461 ) примерно так же хороши как это получается. Я не верю, что обход в ширину помогает в этом случае, так как вы не получите все пути. Например, с ребрами (A,B), (A,C), (B,C), (B,D) и (C,D) вы получите пути ABD и ACD, но не ABCD.

Answer 6

Вот мысль из головы:

1. Найти одно соединение. (Поиск в глубину, вероятно, является хорошим алгоритмом для этого, поскольку длина пути не имеет значения.)
2. Отключить последний сегмент.
3. Попробуйте найти другое соединение с последнего узла до ранее отключенного соединения.
4. Переходите к 2, пока не будет больше соединений.