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

ИНФОРМАЦИЯ: У меня есть массив из 100 узлов, [ 0 .. 99 ]. Каждый узел может иметь произвольное количество связанных узлов:

eg1, 0 ссылки на 5, 10, 15, 20. eg2, 1 ссылки на 30, 40, 50. eg3 и т.д..

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

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

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

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

Источник

5 ответов

Решение

Много чтения / алгоритмов: проблема кратчайшего пути. По сути, вы просто имеете каждое ребро ("ссылка", как вы его назвали) с равным весом.

Источник

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

Источник

Есть ли в этом циклы? то есть это 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;
    }
Источник

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

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

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

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

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

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

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

Пример:

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

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

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

SET = {узел0}
LIST = [[node0, null]]

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

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

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

узел 2 уже находится в наборе. пропустите добавление достижимых узлов в LIST.
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, теперь возвращаемся:

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

Источник

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

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

Источник
Другие вопросы по тегам