Найти пути между двумя данными узлами?

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

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

Единственная проблема с этим состоит в том, если график может быть циклическим.

С соединениями:

• 1, 2
• 1, 3
• 2, 3
• 2, 4

При поиске пути от 1-> 4, у Вас мог быть цикл 1-> 2-> 3-> 1.

В этом случае затем я сохранил бы стек как пересечение узлов. Вот список с шагами для того графика и получающегося стека (извините для форматирования - никакая опция таблицы):

текущий узел (возможные следующие узлы минус, куда мы произошли из) [стек]

1. 1 (2, 3) [1]
2. 2 (3, 4) [1, 2]
3. 3 (1) [1, 2, 3]
4. 1 (2, 3) [1, 2, 3, 1]//ошибка - копируют число на стеке - обнаруженный цикл
5. 3 () [1, 2, 3]//ступивший спиной в узел три и вытолканный 1 от стека. Больше никаких узлов для исследования отсюда
6. 2 (4) [1, 2]//ступивший спиной в узел 2 и вытолканный 1 от стека.
7. 4 () [1, 2, 4]//Целевой найденный узел - записывают стек для пути. Больше никаких узлов для исследования отсюда
8. 2 () [1, 2]//ступивший спиной в узел 2 и вытолканный 4 от стека. Больше никаких узлов для исследования отсюда
9. 1 (3) [1]//ступивший спиной в узел 1 и вытолканный 2 от стека.
10. 3 (2) [1, 3]
11. 2 (1, 4) [1, 3, 2]
12. 1 (2, 3) [1, 3, 2, 1]//ошибка - копируют число на стеке - обнаруженный цикл
13. 2 (4) [1, 3, 2]//ступивший спиной в узел 2 и вытолканный 1 от стека
14. 4 () [1, 3, 2, 4] Целевой найденный узел - записывают стек для пути. Больше никаких узлов для исследования отсюда
15. 2 () [1, 3, 2]//ступивший спиной в узел 2 и вытолканный 4 от стека. Больше никаких узлов
16. 3 () [1, 3]//ступивший спиной в узел 3 и вытолканный 2 от стека. Больше никаких узлов
17. 1 () [1]//ступивший спиной в узел 1 и вытолканный 3 от стека. Больше никаких узлов
18. Сделанный с 2 зарегистрированными путями [1, 2, 4] и [1, 3, 2, 4]

Если Вы хотите все пути, используйте рекурсию.

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

void allPaths(vector<int> previous, int current, int destination)
{
    previous.push_back(current);

    if (current == destination)
        //output all elements of previous, and return

    for (int i = 0; i < neighbors[current].size(); i++)
        allPaths(previous, neighbors[current][i], destination);
}

int main()
{
    //...input
    allPaths(vector<int>(), start, end);
}

Вследствие того, что вектор передается значением (и таким образом любые изменения, внесенные далее вниз в рекурсивной процедуре, не являются постоянными), все возможные комбинации перечисляются.

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

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

Если Вы хотите все кратчайшие пути, используйте предложение Konrad с этим алгоритмом.

То, что Вы пытаетесь сделать, должно по существу найти путь между двумя вершинами в (направленный?) алгоритм Dijkstra выезда графика, если Вы нуждаетесь в кратчайшем пути или пишете простую рекурсивную функцию, если Вам нужны любые пути, существуют.

Исходный код немного громоздок, и вы можете использовать вместо него collection.deque, если хотите использовать BFS, чтобы определить, существует ли путь между двумя точками на графике. Вот быстрое решение, которое я взломал:

Примечание: этот метод может продолжаться бесконечно, если между двумя узлами нет пути. Я не проверял все случаи, YMMV.

from collections import deque

# a sample graph
  graph = {'A': ['B', 'C','E'],
           'B': ['A','C', 'D'],
           'C': ['D'],
           'D': ['C'],
           'E': ['F','D'],
           'F': ['C']}

   def BFS(start, end):
    """ Method to determine if a pair of vertices are connected using BFS

    Args:
      start, end: vertices for the traversal.

    Returns:
      [start, v1, v2, ... end]
    """
    path = []
    q = deque()
    q.append(start)
    while len(q):
      tmp_vertex = q.popleft()
      if tmp_vertex not in path:
        path.append(tmp_vertex)

      if tmp_vertex == end:
        return path

      for vertex in graph[tmp_vertex]:
        if vertex not in path:
          q.append(vertex)