现有算法在非加权图上找到最短路径？

Question

我的任务是编写一个程序，能够找到从一个顶点到另一个顶点的最短移动量。我对'图'的唯一数据是顶点链接到什么顶点，没有权重，距离等。

我必须先解析输入才能找到这些链接。此输入最多可包含1,000,000个顶点。我已经完成了这个。

我看过类似于Dijkstra算法，Floyd算法甚至尝试Q学习的算法。 Dijkstra和Floyd的算法都依赖于顶点之间的距离，Q Learning在处理成千上万的潜在状态和动作时似乎不是最实用的方法。不仅如此，程序必须在提供输入的2秒内找出路径，判断任何类型的强化学习完全没用 - 除非算法能够在两秒内训练数十万条数据。

我可以使用任何现有的算法来实现这一目标吗？如果我必须自己编写，我应该遵循某种一般性指导原则吗？

Answer 1

如果您给出的图形绝对没有指示每个顶点距离结尾有多远，我会建议类似于Dijkstra's。该算法看起来像这样：

The Node object should contain:
    LINKEDNODES = Array of linked nodes
    TRAVELLED = Integer for minimum number of nodes traversed from starting node, initialized as -1
NODES = A given array of nodes
START = the starting node
GOAL = the goal node
QUEUE = Create a priority queue that holds nodes and prioritizes based on their associated TRAVELLED
Give START a TRAVELLED value of 0

MAIN LOOP:
Check front of QUEUE, for each linked node:
   If the node is GOAL then set its TRAVELLED to current node + 1, and go to the next phase RETRACE
   Else If the node's TRAVELLED is -1
   Then set it's TRAVELLED value to current node + 1, and add it to QUEUE
   Otherwise, ignore it, since we don't want to check the same nodes twice

RETRACE:
   CNODE = Current node being checked
   PATH = an array of nodes, of size GOAL.TRAVELLED
   Set CNODE to GOAL
   Repeat until CNODE.TRAVELLED is 0 (which is START's TRAVELLED):
      Add CNODE to PATH
      Set CNODE to the LINKEDNODE of CNODE that has a TRAVELLED of CNODE.TRAVELLED - 1

至于第二个问题，我希望你有一台快速的PC！