Найти все пути между двумя узлами графа

Я работаю над реализацией алгоритма Дейкстры для получения кратчайшего пути между взаимосвязанными узлами в сети маршрутов. У меня работает имплентация. Он возвращает все кратчайшие пути ко всем узлам, когда я передаю начальный узел в алгоритм.

Мой вопрос: как можно найти все возможные пути от узла A, чтобы сказать узел G, или даже все возможные пути от узла A и обратно к узлу A

 HexTree02 мар. 2012 г., 16:31
Вы хотите, чтобы пути не повторяли вершины / ребра?
 GoingMyWay15 мая 2018 г., 15:02
Привет, Пол, ты решил этот вопрос? Вот ссылка, которая может быть полезна для вас:geeksforgeeks.org/find-paths-given-source-destination
 Paul02 мар. 2012 г., 16:52
@ HexTree Я не совсем уверен, что ты имеешь в виду. Каждая вершина уникальна. Я в основном ищу для каждого пути вес этого пути и количество узлов, которые были затронуты через каждый путь
 zmccord02 мар. 2012 г., 16:27
Ну, если у вашего графа есть циклы, это может быть очень длинный список.
 Zruty02 мар. 2012 г., 16:30
Я позволил себе переименовать ваш вопрос, поскольку речь идет не об алгоритме Дейкстры, а о создании путей между узлами графа.

Ответы на вопрос(10)

которая может ответить на ваш вопрос / только она печатает пути, а не собирает их /. Обратите внимание, что вы можете экспериментировать с примерами C ++ / Python в онлайн-среде IDE.

http://www.geeksforgeeks.org/find-paths-given-source-destination/

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

Так как проблема NP-трудна, вы можете сделать вариант поиска в глубину.

По сути, сгенерируйте все возможные пути из A и проверьте, попадают ли они в G.

Если вы действительно хотите упорядочить свои пути от кратчайшего до самого длинного пути, то было бы гораздо лучше использовать модифицированный алгоритм A * или Dijkstra., С небольшой модификацией алгоритм вернет столько возможных путей, сколько вы хотите, в порядке кратчайшего пути. Так что, если вы действительно хотите, чтобы все возможные пути были упорядочены от кратчайшего до самого длинного, то это путь.

Если вам нужна реализация на основе A *, способная возвращать все пути, упорядоченные от самого короткого до самого длинного, то это будет выполнено следующим образом. У этого есть несколько преимуществ. Во-первых, он эффективен при сортировке от самого короткого до самого длинного. Кроме того, он вычисляет каждый дополнительный путь только при необходимости, поэтому, если вы остановитесь рано, потому что вам не нужен каждый отдельный путь, вы сэкономите некоторое время на обработку. Он также повторно использует данные для последующих путей каждый раз, когда вычисляет следующий путь, чтобы сделать его более эффективным. Наконец, если вы найдете какой-то желаемый путь, вы можете прервать его раньше, сэкономив некоторое время вычислений. В целом, это должен быть наиболее эффективный алгоритм, если вам нужна сортировка по длине пути.

import java.util.*;

public class AstarSearch {
    private final Map<Integer, Set<Neighbor>> adjacency;
    private final int destination;

    private final NavigableSet<Step> pending = new TreeSet<>();

    public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
        this.adjacency = adjacency;
        this.destination = destination;

        this.pending.add(new Step(source, null, 0));
    }

    public List<Integer> nextShortestPath() {
        Step current = this.pending.pollFirst();
        while( current != null) {
            if( current.getId() == this.destination )
                return current.generatePath();
            for (Neighbor neighbor : this.adjacency.get(current.id)) {
                if(!current.seen(neighbor.getId())) {
                    final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
                    this.pending.add(nextStep);
                }
            }
            current = this.pending.pollFirst();
        }
        return null;
    }

    protected int predictCost(int source, int destination) {
        return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
    }

    private static class Step implements Comparable<Step> {
        final int id;
        final Step parent;
        final int cost;

        public Step(int id, Step parent, int cost) {
            this.id = id;
            this.parent = parent;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public Step getParent() {
            return parent;
        }

        public int getCost() {
            return cost;
        }

        public boolean seen(int node) {
            if(this.id == node)
                return true;
            else if(parent == null)
                return false;
            else
                return this.parent.seen(node);
        }

        public List<Integer> generatePath() {
            final List<Integer> path;
            if(this.parent != null)
                path = this.parent.generatePath();
            else
                path = new ArrayList<>();
            path.add(this.id);
            return path;
        }

        @Override
        public int compareTo(Step step) {
            if(step == null)
                return 1;
            if( this.cost != step.cost)
                return Integer.compare(this.cost, step.cost);
            if( this.id != step.id )
                return Integer.compare(this.id, step.id);
            if( this.parent != null )
                this.parent.compareTo(step.parent);
            if(step.parent == null)
                return 0;
            return -1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Step step = (Step) o;
            return id == step.id &&
                cost == step.cost &&
                Objects.equals(parent, step.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, parent, cost);
        }
    }

   /*******************************************************
   *   Everything below here just sets up your adjacency  *
   *   It will just be helpful for you to be able to test *
   *   It isnt part of the actual A* search algorithm     *
   ********************************************************/

    private static class Neighbor {
        final int id;
        final int cost;

        public Neighbor(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public int getCost() {
            return cost;
        }
    }

    public static void main(String[] args) {
        final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
        final AstarSearch search = new AstarSearch(adjacency, 1, 4);
        System.out.println("printing all paths from shortest to longest...");
        List<Integer> path = search.nextShortestPath();
        while(path != null) {
            System.out.println(path);
            path = search.nextShortestPath();
        }
    }

    private static Map<Integer, Set<Neighbor>> createAdjacency() {
        final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();

        //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to.
        addAdjacency(adjacency, 1,2,1,5,1);         //{1 | 2,5}
        addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
        addAdjacency(adjacency, 3,2,1,5,1);         //{3 | 2,5}
        addAdjacency(adjacency, 4,2,1);             //{4 | 2}
        addAdjacency(adjacency, 5,1,1,2,1,3,1);     //{5 | 1,2,3}

        return Collections.unmodifiableMap(adjacency);
    }

    private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
        if( dests.length % 2 != 0)
            throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");

        final Set<Neighbor> destinations = new HashSet<>();
        for(int i = 0; i < dests.length; i+=2)
            destinations.add(new Neighbor(dests[i], dests[i+1]));
        adjacency.put(source, Collections.unmodifiableSet(destinations));
    }
}

Вывод из приведенного выше кода выглядит следующим образом:

[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]

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

Наконец, следует отметить, что алгоритмы A * и Dijkstra имеют некоторые незначительные ограничения, хотя я не думаю, что это повлияет на вас. А именно, он не будет работать правильно на графике с отрицательным весом.

Вот ссылка на JDoodle, где вы можете запустить код самостоятельно в браузере и увидеть, как он работает. Вы также можете изменить график, чтобы показать, что он работает и на других графиках:http://jdoodle.com/a/ukx

что вам нужна какая-то форма алгоритма Форда-Фулкерсона, основанная на BFS. Он используется для расчета максимального потока в сети путем нахождения всех путей расширения между двумя узлами.

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

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

 Diego02 мар. 2012 г., 16:32
Это просто, эффективно и выполнимо для любого DAG. Вы вводите в заблуждение @Paul.

Вот алгоритм поиска и печати всех путей от s до t с использованием модификации DFS. Также динамическое программирование может использоваться, чтобы найти количество всех возможных путей. Псевдокод будет выглядеть так:

 C[1...n]    //array of integers for storing path count from 's' to i
 TopologicallySort(G(V,E))  //here suppose 's' is at i0 and 't' is at i1 index

  for i<-0 to n
      if i<i0
          C[i]<-0  //there is no path from vertex ordered on the left from 's' after the topological sort
      if i==i0
         C[i]<-1
      for j<-0 to Adj(i)
          C[i]<- C[i]+C[j]

 return C[i1]

все Возможные пути - сложная проблема, так как существует экспоненциальное число простых путей. Даже нахождение k-го кратчайшего пути [или самого длинного пути]NP-Hard.

Одно из возможных решений - найти все пути [или все пути до определенной длины] изs вt являетсяBFSбез сохраненияvisited установить или для взвешенной версии - вы можете использоватьпоиск единой стоимости

Обратите внимание, что также в каждом графе, который имеет циклы [это неDAG] может быть бесконечное количество путей междуs вt.

 william00701 февр. 2013 г., 03:03
@amit это тоже можно сделать в DFS?
 amit01 февр. 2013 г., 10:09
@ william007: Конечно, вы можете, но будьте осторожны, что вы можете застрять в цикле и через некоторое время перестать давать ответы. Однако - чтобы получить всепросто пути от А до Г - DFS это путь, и вашvisited set is per path (то есть, когда вы вернетесь из рекурсии, удалите элемент из набора, прежде чем переходить к следующему узлу).
 amit17 авг. 2015 г., 18:42
@VShreyas Это своего рода старая ветка, в ответе конкретно говорится «все пути до определенной длины», и это можно сделать с помощью BFS без посещения набора. Если вы хотите, чтобы всепросто пути между двумя узлами, вы можете сделать это с DFS с «локальным» посещенным набором (который удаляет узел из посещенного набора, когда он отслеживает назад).
 amit02 мар. 2012 г., 17:06
@Paul: Добро пожаловать. просто убедитесь, что в обоих из них вы не используетеvisited установить [как предлагает оригинальный алгоритм] или вы получите только часть путей. Кроме того, вы должны ограничить пути определенной длиной, чтобы избежать бесконечных циклов [если граф имеет циклы ...]. Удачи!
 Paul02 мар. 2012 г., 17:01
Спасибо, я попробую посмотреть на BFS или поиск единой стоимости

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

Вот некоторый код Java, который демонстрирует то, что я реализовал. Я уверен, что должны быть более эффективные или изящные способы сделать это также.

Stack connectionPath = new Stack();
List<Stack> connectionPaths = new ArrayList<>();
// Push to connectionsPath the object that would be passed as the parameter 'node' into the method below
void findAllPaths(Object node, Object targetNode) {
    for (Object nextNode : nextNodes(node)) {
       if (nextNode.equals(targetNode)) {
           Stack temp = new Stack();
           for (Object node1 : connectionPath)
               temp.add(node1);
           connectionPaths.add(temp);
       } else if (!connectionPath.contains(nextNode)) {
           connectionPath.push(nextNode);
           findAllPaths(nextNode, targetNode);
           connectionPath.pop();
        }
    }
}
 arslan03 февр. 2016 г., 10:25
есть нерекурсивная версия этого?
 Omer Hassan03 февр. 2016 г., 11:23
У меня его нет, нет, но я думаю, что теоретически любую рекурсивную программу можно преобразовать в нерекурсивную, я думаю, используя что-то вроде стекового объекта, смысл в том, чтобы эмулировать то, что на самом деле делает рекурсивная программа Я полагаю, используя пространство стека программы. Вы можете посмотреть принцип преобразования рекурсивных программ в нерекурсивные.
find_paths [s, t, d, k]

Я лично нахожу алгоритм видаfind_paths[s, t, d, k] полезно, где:

s является начальным узломt является целевым узломd - максимальная глубина для поискаk - количество путей для поиска

Используя форму бесконечности вашего языка программирования дляd а такжеk даст вам все пути§.

§ очевидно, если вы используете ориентированный граф и хотите, чтобы всененаправленный пути междуs а такжеt вам придется запустить это в обе стороны:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Вспомогательная функция

Мне лично нравится рекурсия, хотя иногда это может быть сложно, так или иначе, давайте сначала определим нашу вспомогательную функцию:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()
Основная функция

При этом основная функция тривиальна:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

Во-первых, давайте заметим несколько вещей:

Приведенный выше псевдокод представляет собой смесь языков - но наиболее сильно напоминает python (поскольку я просто кодировал в нем). Строгая копия-вставка не сработает.[] является неинициализированным списком, замените его на эквивалентный для вашего языка программирования по вашему выборуpaths_found проходит мимоссылка, Понятно, что функция рекурсии ничего не возвращает. Обращайтесь с этим соответствующим образом.Вотgraph предполагает некоторую формуhashed структура. Существует множество способов реализации графа. Так или иначе,graph[vertex] получает список соседних вершин внаправленный график - настроить соответственно.это предполагает, что вы предварительно обработали удаление "застежек" (циклов), циклов и мульти-ребер

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

Я собираюсь доказать, что сложность времени для перечисления всех простых путей между двумя выбранными и различными узлами (скажем,s а такжеt) в произвольном графеG не является полиномом. Обратите внимание, что, поскольку мы заботимся только о количестве путей между этими узлами, пограничные расходы не имеют значения.

Конечно, если у графа есть некоторые правильно выбранные свойства, это может быть легко. Я рассматриваю общий случай все же.

Предположим, что у нас есть полиномиальный алгоритм, который перечисляет все простые пути междуs а такжеt.

ЕслиG подключен, список не пуст. ЕслиG нет иs а такжеt находятся в разных компонентах, очень легко перечислить все пути между ними, потому что их нет! Если они находятся в одном и том же компоненте, мы можем делать вид, что весь граф состоит только из этого компонента. Итак, давайте предположим,G действительно связано.

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

Мы можем показать (хотя я не могу придумать связного способа сказать это), что этот самый длинный путь должен пройти через все вершиныG, Таким образом, мы только что нашлиГамильтонов путь с полиномиальной процедурой! Но это хорошо известная NP-сложная проблема.

Затем мы можем заключить, что этот полиномиальный алгоритм, который мы думали,очень маловероятно существовать, если толькоP = NP.

 araruna07 июн. 2014 г., 14:18
Просто быть чистым. Если бы направленная версия могла быть решена за многократное время, ее ответ дал бы ответ на направленный гамильтонов путь. Более того, если бы у нас были взвешенные ребра, можно показать, что полиномиальным процессом мы могли бы ответить на задачу коммивояжера.
 araruna07 июн. 2014 г., 14:08
Ну, да, но вы могли бы использовать свой алгоритм, чтобы ответить, существует ли направленный гамильтонов путь аналогичным образом, который также является NP-полным. Если ваш ответn-1тогда есть. Если это не так, тогда не может быть такого пути, иначе он будет длиннее, чем ваш самый длинный.
 boycy06 июн. 2014 г., 23:31
Если я правильно понимаю, то это доказательство работает только для неориентированных графов, поскольку в ориентированном графе утверждение, что «этот самый длинный путь должен пересекать все вершиныG"не обязательно имеет место. Это правильно?

Ваш ответ на вопрос