Все пути между 2 узлами в графе

Question

Мне нужно создать программу неинформированного поиска (Breadth-first-Search), которая берет два узла и возвращает все пути между ними.

public void BFS(Nod start, Nod end) {
            Queue<Nod> queue = new Queue<Nod>();
            queue.Enqueue(start);
            while (queue.Count != 0)
            {
                Nod u = queue.Dequeue();
                if (u == end)  break;
                else
                {
                    u.data = "Visited";
                    foreach (Edge edge in u.getChildren())
                    {
                        if (edge.getEnd().data == "")
                        {
                            edge.getEnd().data = "Visited";
                            if (edge.getEnd() != end)
                            {
                                edge.getEnd().setParent(u);
                            }
                            else
                            {
                                edge.getEnd().setParent(u);
                                cost = 0; 
                                PrintPath(edge.getEnd(), true);
                                edge.getEnd().data = "";
                                //return;
                            }
                        }
                        queue.Enqueue(edge.getEnd());
                    }
                }
            }
        }

Моя проблема в том, что я получаю только два пути вместо всех, и я не знаю, что редактировать в моем коде, чтобы получить их все.Ввод моей проблемы основан на этой карте:

Answer 1

В алгоритме BFS вы не должны останавливаться после того, как найдете решение. Одна из идей состоит в том, чтобы установить нулевые данные для всех городов, которые вы посетили, кроме первого, и позволить функции работать немного дольше. У меня нет времени написать вам фрагмент, но если вы его не получите, я напишу хотя бы псевдокод. Если вы не поняли мою идею, оставьте комментарий со своим вопросом, и я постараюсь объяснить лучше.

Answer 2

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

Возьмем простой пример

1----2
 \    \
  3--- 4----5

Нам нужны все пути от 1 до 5. Мы ставим в очередь 1, затем 2 и 3, затем 4, затем 5. Мы потеряли тот факт, чтоЕсть два пути от 4 до 5.

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

Answer 3

Путь - это последовательность вершин, в которой ни одна вершина не повторяется более одного раза. Учитывая это определение, вы могли бы написать рекурсивный алгоритм, который будет работать следующим образом: передать в функцию четыре параметра, назвать ее F(u, v, intermediate_list, no_of_vertices), где u - текущий источник (который изменится при повторном использовании), v intermediate_list - это список вершин, который изначально должен быть пустым, и каждый раз, когда мы используем вершину, мы добавляем его в список, чтобы избежать использования вершины более одного раза в нашем пути, а no_of_vertices - это длина пути, который мы хотели бы найти, который должен быть ограничен снизу 2, а верхний ограничен V - числом вершин. По сути, функция должна возвращать список путей, чей источник u, пункт назначения v и длина каждого пути no_of_vertices. Создайте начальный пустой список и сделайте вызовы F(u, v, {}, 2), F(u, v, {}, 3), ..., F(u, v, {}, V), каждый раз объединяя выходные данные F со списком, в котором мы намерены хранить все пути. Попробуйте реализовать это, и если у вас все еще возникнут проблемы, я напишу для вас псевдокод.

Редактировать: Решение вышеуказанной проблемы с использованием BFS: поиск в ширину - это алгоритм, который можно использовать для изучения всех состояний графа. Вы можете изучить график всех путей данного графа, используя BFS, и выбрать пути, которые вы хотите. Для каждой вершины v добавьте следующие состояния в очередь: (v, {v}, {v}), где каждое состояние определено как: (current_vertex, list_of_vertices_already_visited, current_path). Теперь, пока очередь не пуста, откройте верхний элемент очереди, для каждого ребра e из current_vertex, если в list_of_vertices_already_visited хвостовая вершина x еще не существует, нажмите Новое состояние (x, list_of_vertices_already_visited + {x}, current_path -> x) в очереди, и обрабатывать каждый путь, когда вы извлекаете его из очереди. Таким образом, вы можете искать весь график путей для графика, будь то направленный или ненаправленный.

Answer 4

Звучит как домашнее задание.Но забавный вид.

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

class Node{
  Vector[Link] connections;
  String name;
}

class Link{
  Node destination;
  int distance;
}

Vector[Vector[Node]] paths(Node source, Node end_dest, Vector[Vector[Node]] routes){
  for each route in routes{
    bool has_next = false;
    for each connection in source.connections{
      if !connection.destination in route {
        has_next = true;
        route.push(destination);
        if (!connection.destination == end_dest){
          paths(destination, end_dest, routes);
        }
      }
    }
    if !has_next {
      routes.remove(route) //watch out here, might mess up the iteration
    }
  }
  return routes;
}

Изменить: Это действительно ответ на вопрос, который вы ищете? Или вы действительно хотите найти кратчайший путь? Если это последний, используйте алгоритм Дейкстры: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm