在有向图（Digraph）中，由一个节点（Vertex）沿着边（Edge）可以到达的节点称为其 ancestor（祖先）。当两个不同节点拥有一个共同 ancestor 时，该 ancestor 称这两个节点的 Common Ancestor （共同祖先），Shortest Ancestral Path （SAP，最短祖先路径）即所有 common ancestor 中到两个节点路径之和最短的一个及其对应的路径。

SAP 算法在许多领域都有应用，比如在生物进化学中，所有生物的进化历程可以概括为一个无环有向图（参见 维基百科:Tree of life(biology)），那么 SAP 算法可以在该有向图中找出两种生物的最近共同祖先。

算法简介及API

辅助类

以下为提供的辅助类：

• Digraph (有向图类)

• BreadthFirstSearchPath (利用广度搜索的最短路径类)

*以下使用 distance(v -> s) 代表方法 BreadthFirstSearchPath(G, v).disTo(s)

SAP

SAP 类需要在初始化时接受一个Digraph类的实例，length() 及 ancestor() 方法分别接收两个参数（节点或节点集）并返回找到的 SAP 最短路径长度及节点，当不存在该 common ancestor 时返回 -1。当接收的参数为节点集时，返回值为节点集 v 中任一节点与节点集 w 中任一节点的所有 SAP 中长度最小的一个。

全局遍历

在 Digraph 中寻找两个节点 v， w 之间的 SAP 最简单的粗暴的方式就是直接遍历。 类 BreadthFirstSearchPath(Digraph G, int v) 初始化后，通过方法 hasPathTo(int s) 能够判断是否有从 v 到 s 的路径，方法 disTo(int s) 能够得到从 v 到 s 的路径长度。 当某个节点同时存在从 v 与 w 出发的路径时，则该节点为 common ancestor，遍历 Digraph 中所有节点找出所有的 common ancestor，并找出其中到 v 与 w 路径之和最短的即可。

该方法能够找出所需的 SAP ，但遍历 Digraph 中的所有节点运行效率极低。

镜面法

参考物理中寻找通过镜面反射的最短光路问题。将 SAP 节点称为 a ，那么在 Digraph 中 distance(v -> a) + distance(w -> a) 最小等价于 Digraph 中 distance(v -> a) 与 Digraph.reverse 中 distance(a' -> w') 之和最小。

建立一个大小为 2*V 的 NewDigraph，其中 V 个节点代表 Digraph 中的节点（s），并按照 Digraph 中的边连接；另外 V 个节点代表 Digraph.reverse 中的节点（s’），并按照 Digraph.reverse 中的边连接（镜子中的虚像，边的连接方向相反）。然后将代表 Digraph 中每个节点 s 与代表 Digraph.reverse 中的对应节点 s’ 连接起来 NewDigraph.addEdge(s -> s') (将实像与虚像相连)。这样，当寻找 v 与 w 的 SAP 时，在 NewDigraph 中寻找 v -> w’ 的最短路径即可（Breadth First Search），而该最短路径比 SAP 路径长 1 （多 a -> a’ 一步），SAP 路径的 common ancestor 即为穿过镜子的点 a (在路径中表现为 a 与 a’ 相连，且区分实像与虚像点)。

该方法实现起来简单，但弊端十分明显。其将有向图节点数增加了一倍（V -> 2*V） 边数增加了 V+E （E -> E+E+V）,那么程序所占用的内存也要增加不止一倍。更为重要的是，虽然在这个扩大的有向图中能够通过 BFS 找到 SAP 但需要遍历的节点与边数大大增加，程序的运行效率依旧很低。

从起点遍历

既然要寻找以 v 和 w 为起点的路径，那么直接从 v 和 w 开始遍历会更为有利。搜索的执行步骤如下：

1. 将起点 v 和 w 加入 Queue 中，v 和 w 与遍历起点的距离 distanceToStart 为0；
2. 从 Queue 中取出一个节点 s ，如果其父节点（Digraph.adj()）未被遍历，将其加入队列，对应的与遍历起点的距离为 distanceToStart(s) + 1，标记为已遍历；
3. 测试起点 v, w 是否都有路径到达 s，如果有，则 s 为 common ancestor，记录该节点，并将该节点到 v， w 的距离之和( distance(v -> s) + distance(w -> s) )设置为当前找到的 SAP 路径长度；
4. 重复步骤 2-4 直到 Queue 为空。

该方法与 Breadth First Search 的思想相似。但仍可以继续优化，设置提前结束条件。在 Queue 中读出的节点与遍历起点的距离是递增的，而且 s 到 起点 v， w 的距离之和一定不小于 s 与遍历起点的距离（v， w 中的一个就是遍历起点，到另一个的距离一定 >= 0）。当 s 与遍历起点的距离大于当前找到的最短路径长度时，则可以提前结束遍历，因为之后找到的所有顶点到 v， w 的距离之和一定更大。

该方法只会遍历有限的节点，当找到的 SAP 路径长度足够小时会提前结束遍历，能够快速找出 SAP。

自定义 BreadthFirstSearchPath

如果分析上节从起点遍历中的方法会发现，执行效率进一步提高的瓶颈来自于类 BreadthFirstSearchPath 的初始化。

使用方法 disTo(s) 得到 distance(v -> s) 之前需要向 BreadthFirstSearchPath 传入 Digraph 与路径起点 v 进行初始化。 在该类的实现中，初始化过程会使用 Breadth First Search 遍历起点 v 的所有 ancestor 节点并记录到起点的距离，之后在调用方法 disTo(s) 时直接返回保存的距离值。

换言之，在寻找 v 与 w 的 SAP 之前，要预先计算 v 与 w 的所有 ancestor 节点的距离，再根据得到的距离寻找 SAP。但是不是每次寻找都会用到所有的 ancestor 节点，特别是 SAP 节点距离起点较近时，大部分 ancestor 节点的距离计算是“毫无意义”的。因此，为了进一步提高算法效率，可以实现自己的 BreadthFirstSearchPath 方法，将距离的计算与 common ancestor 的寻找结合到一次 Breadth First Search 中，在找到所需 SAP 时停止寻找。基本执行步骤与上节中的搜索执行步骤十分相似，只是需要保存的数据不同：

1. 将起点 v 和 w 加入 Queue 中同时区分标记节点的来源，v 和 w 与各自遍历起点的距离 distanceToV (或 distanceToW) 为0；
2. 从 Queue 中取出一个节点 s ，如果 s 到其来源起点的距离大于当前已知的 SAP 路径长度，停止遍历；
3. 如果 s 的父节点（Digraph.adj()）未被 s 的来源方向遍历，将其加入队列，其与来源遍历起点的距离为 distanceToV(s) + 1（或 distanceToW(s) + 1），同时标记为已从来源方向遍历；
4. 测试 s 是否已被 v， w 两个方向遍历，如果是，则 s 为 common ancestor，记录该节点，并将该节点到 v， w 的距离之和( distanceToV(s) + distanceTow(s) )设置为当前找到的最短路径长度；
5. 重复步骤 2-5 直到 Queue 为空。

顶点集输入

前文讨论了单顶点输入下的算法，对于顶点集（多顶点）输入的情况处理与单顶点相同，只是将每个方向的起点由一个增加为多个，由于 Breadth First Search 的特性，在遍历过程中找到的顶点与起点的距离一定是与所有的来源方向起点距离中最小的一个。最后得到的结果也会符合 节点集 v 中任一节点与节点集 w 中任一节点的所有 SAP 中长度最小的一个的要求。