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

Question

INFO: У меня есть массив из 100 узлов, [0 .. 99]. Каждый узел может иметь произвольное количество связанных узлов:

eg1, 0 ссылки на 5, 10, 15, 20. eg2, 1 ссылки на 30, 40, 50. например, 3 и т.д ..

Все 100 узлов имеют хотя бы один связанный узел, узлы не знают, кто на них ссылается.

ВОПРОС: Как я могу найти кратчайший путь ссылки, если предоставляется START и END.

например. START = 5, END = 80, путь ссылки (пример): [5] -> 10-> 24-> 36 -> [80]?

Я использую Pascal и / или PHP, но понимание того, что я ищу [код тоже помогает].

Answer 1

Много чтения / алгоритмы: Проблема кратчайшего пути . Фактически, у вас есть все ребра («ссылка», как вы их назвали) с равным весом.

Answer 2

Две структуры: набор и список.

В наборе вы сохраняете уже посещенные узлы. Это предотвращает вас от следующих циклов.

Список состоит из объектов, содержащих: (1) узел и (2) указатель на узел, который его нашел.

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

Затем для каждого элемента в списке, вплоть до достижения конца, выполните следующее:

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

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

Пример:

Даны узлы от 0 до 3, где
узел0 -> узел1
узел0 -> узел2
узел1 -> узел2
узел2 -> узел3
и node0 это START, а node3 это END

SET = {}
СПИСОК = []

Шаг 1 - добавить START:

SET = {node0}
LIST = [[node0, null]]

Шаг 2 - по индексу 0 списка - добавить достижимые узлы:

SET = {узел0, узел1, узел2}
LIST = [ [узел0, ноль] , [узел1, 0], [узел2, 0]]

Шаг 3 - в индексе 1 из LIST - добавить достижимые узлы:

узел 2 уже находится в наборе. пропустите добавление доступных узлов в СПИСОК.
SET = {узел0, узел1, узел2}
LIST = [[node0, null], [node1, 0] , [node2, 0]]

Шаг 4 - в индексе 2 LIST - добавить достижимые узлы:

SET = {узел0, узел1, узел2, узел3}
LIST = [[node0, null], [node1, 0], [node2, 0] , [node3, 2]]

Шаг 5 - достиг КОНЦА, теперь возвращаемся назад:

Узел END (узел 3), вставленный в СПИСОК, имеет обратную ссылку на индекс 2 в списке, который является узлом 2. Это обратная ссылка на индекс 0 в списке, который является node0 (START). Инвертируйте это, и вы получите кратчайший путь node0 -> node2 -> node3.

Answer 3

Есть ли в этом циклы? то есть это DAG?

Если циклов нет:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {   
       //If this is the node you are looking for...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the end node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       List<Node> bestPath = null;

       foreach(Node child in startNode.Children)
       {             
          //get the shortest path from this child
          List<Node> childPath = GetShortestPath(child, endNode);
          if (childPath != null &&
             ( bestPath == null || childPath.Count < bestPath.Count))
          { 
              bestPath = childPath;
          }
       }

       bestPath.Insert(0, startNode);
       return bestPath;
    }

[Редактировать: Добавлен пример для циклов] Если могут быть циклы:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {
        List<Node> nodesToExclude = new List<Node>();
        return GetShortestPath(startNode, endNOde, nodesToExclude);
   }

   List<Node> GetShortestPath(Node startNode, Node endNode, List<Node> nodesToExclude)
   {   
       nodesToExclude.Add(startNode);

       List<Node> bestPath = null;

       //If this is end node...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the child node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       foreach(Node child in startNode.Children)
       {
          if (!nodesToExclude.Contains(child))
          {
              //get the shortest path from this child
              List<Node> childPath = GetShortestPath(child, endNode);
              if (childPath != null &&
                 ( bestPath == null || childPath.Count < bestPath.Count))
              { 
                  bestPath = childPath;
              }
          }
       }

       nodesToExclude.Remove(startNode);
       bestPath.Insert(0, child);

       return bestPath;
    }

Answer 4

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

Answer 5

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

Думайте об этом так: скажем, вы выполняете скрытную миссию, чтобы найти симпатичных цыпочек в вашем районе. Вы начинаете в своем собственном доме и отмечаете его как СТАРТ. Вы бы потом пошли стучать в своих ближайших соседей, верно? Итак, мы сделаем именно это - поместим все узлы, подключенные к началу, в очередь. Теперь повторите поиск соседей для всех узлов в этой очереди. И продолжай делать это, пока не получишь свою девушку, ну, ЭНД.