线性阵列节点随机链接到阵列中的其他节点，最短路径

Question

信息： 我有一个由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，但了解我在找什么[代码也有帮助]。

Answer 1

大量阅读/算法： Shortest path problem。你实际上只是拥有同样重要的每一个边缘（就像你称之为“链接”）。

Answer 2

这是树/图还是森林？如果它是森林，则路径可能无法一直定义。如果这是一个树/图，请尝试使用广度优先搜索。

想想这样：比如说，你在隐秘的任务中寻找可爱的小鸡在你的邻居。你从自己的家开始，并将其标记为START。接下来你会去敲你最近的邻居吧？因此，我们将这样做 - 将所有连接到队列开始的节点都推送到队列中。现在，重复搜索此队列中所有节点的邻居。并继续这样做，直到你得到你的女孩，呃，结束。

Answer 3

执行从Start节点开始的广度优先遍历，并在找到最终节点后立即退出。

Answer 4

这是否有周期？即它是一个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 5

两种结构：一组和列表。

在该集合中，存储已经访问过的节点。这会阻止您遵循循环。

该列表是包含以下对象的列表：（1）节点，以及（2）返回到找到它的节点的指针。

从开始节点开始，将它添加到集合中，用空回引用将它添加到列表中，然后将其可以到达列表的所有节点添加到列表中对索引0的反向引用（起始节点）。

然后其后列表中的每个元素，直到你到达终点，请执行下列操作：

1. 如果是在设定已经跳过它（你已经访问过它），并移动到列表中的下一项。
2. 否则，将其添加到该集合中，并将其可以到达的所有节点添加到列表的末尾，并将反向引用添加到您正在查看的索引中。然后转到列表中的下一个索引并重复。

如果您在任何时候到达终端节点（最好是因为您将它添加到列表中 - 而不是在列表中访问它），请通过对起始节点的反向引用进行跟踪并将反转路径。

实施例：

鉴于节点0至3，其中
NODE0 - >节点1
NODE0 - >节点2
节点1 - >节点2
节点2 - >节点3
和NODE0是START和节点3是END

SET = {}
LIST = []

步骤1 - 添加STAR T：

SET = {NODE0}
LIST = [[NODE0，空]]

步骤2 - 在该列表的索引0 - 添加可达节点：

SET = {NODE0 ，节点1，节点2}
LIST = [[NODE0，空]，[节点1，0]，[节点2，0]]

步骤3 - 在该列表的索引1 - 添加可达节点：

node2已经在SET中。跳过将可达节点添加到LIST。
SET = {NODE0，节点1，节点2}
LIST = [[NODE0，空]，[节点1，0]，[节点2，0]]

步骤4 - 在索引2列表 - 添加可达节点：

SET = {NODE0，节点1，节点2，节点3}
LIST = [[NODE0，空]，[节点1，0]，[节点2，0]，[节点3，2 ]]

第5步 - 到达END，no w回溯：

插入到列表中的END节点（node3）对列表中的索引2具有反向引用，该索引是node2。这对列表中的索引0有一个反向引用，即node0（START）。反转这一点，你会得到node0 - > node2 - > node3的最短路径。