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

Question

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

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

我研究过类似于并包括 Dijkstra 算法、Floyd 算法的算法，甚至尝试过 Q Learning。 Dijkstra 和 Floyd 算法都依赖于顶点之间的距离，而 Q Learning 在处理数十万种潜在状态和 Action 时似乎并不是最实用的方法。不仅如此，程序还必须在提供输入后的 2 秒内找出路径，裁定任何类型的强化学习都是完全无用的——除非该算法可以在两秒内训练数十万条数据。

我可以使用任何现有算法来实现这个目标吗？如果我必须自己编写，是否应该遵循某种通用准则？

Answer 1

如果给你的图完全没有指示每个顶点离末端有多远，我会建议类似于 Dijkstra 的。该算法看起来像这样:

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!