0

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

4

5 回答 5

2

大量阅读/算法： 最短路径问题。您实际上只是让每条边（如您所说的“链接”）具有相同的权重。

于 2009-02-18T19:07:34.773 回答
1

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

于 2009-02-18T19:10:45.983 回答
1

这有循环吗？即它是一个 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;
    }
于 2009-02-18T19:26:00.783 回答
1

两种结构：集合和列表。

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

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

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

然后对于列表中的每个元素，直到到达末尾，执行以下操作：

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

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

例子：

给定节点 0 到 3，其中
node0 --> node1
node0 --> node2
node1 --> node2
node2 --> node3
and node0 为 START 而 node3 为 END

设置 = {}
列表 = []

第 1 步 - 添加开始：

SET = {node0}
列表 = [[node0, null]]

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

SET = {node0, node1, node2}
LIST = [ [node0, null] , [node1, 0], [node2, 0]]

第 3 步 - 在 LIST 的索引 1 - 添加可达节点：

node2 已经在 SET 中。跳过将可达节点添加到 LIST。
SET = {node0, node1, node2}
LIST = [[node0, null], [node1, 0] , [node2, 0]]

第 4 步 - 在 LIST 的索引 2 - 添加可达节点：

SET = {node0, node1, node2, node3}
LIST = [[node0, null], [node1, 0], [node2, 0] , [node3, 2]]

第 5 步 - 到达 END，现在回溯：

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

于 2009-02-18T19:35:08.250 回答
0

这是一棵树/图还是一片森林？如果是森林，则路径可能并不总是被定义。如果这是一个树/图，请尝试使用广度优先搜索。

可以这样想：比如说，你正在执行一项秘密任务，在附近寻找可爱的小鸡。您从自己的房子开始，并将其标记为开始。你接下来会去敲你最近的邻居，对吧？所以，我们将这样做——将所有连接到队列的节点推入队列中。现在，对该队列中的所有节点重复邻居搜索。并继续这样做，直到你得到你的女孩，错误，结束。

于 2009-02-18T19:09:07.813 回答