如何在有向图中以线性时间找到两个顶点之间不同最短路径的数量？

Question

这是练习题：

假设有一个有向图 G=(V,E)，其中 v 和 w 是两个顶点。请设计一种线性时间复杂度算法，用于查找 v 和 w 之间不同的最短路径数量（路径不一定要求顶点不重复）。注意：G 中的边都是没有权重的。

总结一下：

1. G 是一个有向图；
2. 需要找到最短路径的数量；
3. 需要考虑 v 到 w 和 w 到 v 两个方向上的路径；
4. 算法需要是线性时间复杂度；
5. G 的边没有权重。

基于以上的条件，我的想法如下：

1. 由于 G 中的边没有权重，并且我们需要找到所有的最短路径而不是单一路径，因此不需要使用 Dijkstra’s Algorithm；
2. 我需要维护一个变量 count 来记录最短路径的数量；
3. 我打算使用 BFS 从 v 开始遍历整个图，并维护一个全局层数的信息；
4. 每当 BFS 遍历到一个新的层数时，我将全局层数增加 1；
5. 我还需要维护到顶点 w 的最短路径长度的信息；
6. 当 BFS 遍历到 w 时，如果当前的全局层数等于最短路径长度，那么将 count 增加 1，并将全局层数赋值给最短路径长度；
7. 只要全局层数等于最短路径长度，就每次遍历到 w 就将 count 增加 1；
8. 当全局层数大于最短路径长度时，就可以终止遍历。因为我们要找到的是最短路径而不仅仅是路径。
9. 然后再从 w 开始做一遍 v 到 w 的操作即可。

我的算法正确吗？如果我先从 v 到 w 再从 w 到 v，这仍然被认为是线性时间复杂度吗？

- Jackson Tale

Answer 1

以下是一些解决方法。

• 从v到w只有在通过节点x时出现多个最短路径，这要么是因为通过同一顶点进入x的多条路径，要么是因为在同一DFS层次中多次遇到x。

证明：如果有多条路径通过相同的顶点进入x，那么显然有多种途径通过x。这很简单。现在假设每个进入x的顶点最多只有一种方式。

如果之前已经遇到过x，则当前路径都无法对另一个最短路径做出贡献。由于之前已经遇到了x，随后的所有路径长度都至少比先前的最短路径长1。因此，这些路径都不能对总和做出贡献。

这意味着我们最多遇到每个节点一次，然后就完成了。因此，正常的BFS就足够了。

• 我们甚至不需要知道层级，而可以在遇到最终节点时得到最终数字。

这可以编译成一个非常简单的算法，主要是BFS。

 - Mark nodes as visited as usual with BFS.
 - Instead of adding just nodes to the queue in the DFS add nodes plus number of incoming paths.
 - If a node that has been visited should be added ignore it.
 - If you find a node again, which is currently in the queue, do not add it again, instead add the counts together.
 - Propagate the counts on the queue when adding new nodes.
 - when you encounter the final, the number that is stored with it, is the number of possible paths.

- LiKao

---

我必须标记qrqrq的答案，因为他首先指出了我的解决方案的缺陷，并引导了你们之间的良好讨论。 - Jackson Tale

只是想指出 - @qrqrq 是错误的 - 你的解决方案并不有缺陷；在最坏情况下也不需要指数时间。你只需要使用修改过的BFS算法即可。 - Dan Nissenbaum

@DanNissenbaum 好的，我会再仔细研究这些答案。我原本认为qrqrq的回答是正确的，因为我的BFS确实不会考虑qrqrq提出的情况，因为我的解决方案旨在使用标准BFS，它会经过每条边并且只处理每个顶点一次。但是要处理qrqrq提出的情况，就像你说的那样，我必须稍微修改我的BFS。 - Jackson Tale

这是一种情况，你问题中的算法大致上是正确的，主要思想是正确的（使用BFS方法是正确的，并且它在线性时间内运行），但是算法并没有完全不变地成功。因此，严格来说，你的算法，就其书写方式而言，似乎失败了，但是主要思想是正确的。因此，当事实上主要思想是正确的时，声称你的算法失败是具有误导性的 - 即使从技术上讲，“算法失败”是正确的。 - Dan Nissenbaum

你们两个都是正确的。我会标记这个答案。 - Jackson Tale

Answer 2

你的算法会在如下图所示的图中出现问题：

  *   *   *   1
 / \ / \ / \ / \
v   *   *   *   w
 \ / \ / \ / \ /
  *   *   *   2

对于所有边都从左到右定向的情况进行计数。它计算了两条路径，一条通过1，另一条通过2，但是1和2都可以通过八条不同的最短路径从v到达，因此总共有十六条路径。

- qrqrq

---

我认为你是正确的。那么，修改我的算法如何呢？当进行BFS时，我将删除“已发现”的状态，而使用“已处理”来检查是否经过了一个顶点？ - Jackson Tale

在这方面正确的算法需要指数时间 -- 每个新的常量大小的“褶皱”都会使要计算的路径数量翻倍。 - qrqrq

实际上，我认为可以通过将每个节点与一个“成功计数”相关联来避免指数时间，该计数跟踪该节点下方的成功路径数量及其长度。修改后的BFS算法在递归退出时更新成功计数（将成功计数传递给上一级）。当BFS算法到达先前已被访问过的节点时（此次访问是BFS算法的一部分），它会避免递归并仅将成功计数结果传递回上一级。 - Dan Nissenbaum

@qrqrq：只有在您想要实际输出所有最短路径时才适用。如果您只需要数量，我认为这是可以完成的，因为您不必遵循所有最短路径。 - LiKao

如果你真的花时间读了我写的内容，那不是我说的。 - qrqrq

@qrqrq：也许你说“沿着这些线路的正确算法在最坏情况下需要指数时间”这个陈述给人留下了错误的印象。因为沿着这些线路的正确算法（即修改后的BFS）不需要EXPTIME。一个简单的修改后的BFS可以在O(N)的时间内正确完成。然而，什么应该被认为是“沿着这些线路的正确算法”可能不太清楚。 - LiKao

Answer 3

如qrqrq所示，您的算法在某些图形上失败，但BFS的思想是好的。相反，维护一个大小为|V|的数组z，将其初始化为零；在z[i]中保留到距离小于level的已发现顶点i的最短路径数。还要维护一个大小为|V|的数组d，使得如果距离小于level，则d[i]是从v到顶点i的距离。将level初始化为0，将d[v]初始化为0，将z[v]初始化为1（从v到v有一条长度为0的路径），并将d和z的所有其他条目设置为-1和0。

现在，每当您在BFS中遇到从i到j的边缘时，那么：

• 如果d[j] = -1，则将d[j]：= level和z[j]：= z[i]设置。

• 如果d[j] = level，则将z[j]：= z[j] + z[i]设置。

• 否则，什么也不做。

原因是对于从v到i的每条最短路径，都有一条从v到j的最短路径。这将以线性时间给出从v到每个顶点的最短路径数。现在再次从w开始执行相同的操作。

- Erik P.

---

@LiKao - 或许更好的做法是让提问者决定哪个解决方案更简单，即使在显而易见的情况下也是如此。这样会更加谦逊。 - Dan Nissenbaum

@LiKao，那其实只是同一个解决方案的不同描述 :) - Erik P.

@ErikP.：哦，我以为那是另外一回事。在我的解决方案中，我既不跟踪级别，也不从“w”进行任何搜索。只需从“v”到“w”进行一次BFS遍历即可。也许我只是被解释搞糊涂了，而你的意思并非我所想的。 - LiKao

@ErikP.：好的，我现在明白了……我之前理解有误。你的方法和我的完全一样，只不过你使用了级别数组来构建最终集合。 - LiKao

@JacksonTale：如果你需要决定是选择他的还是我的，那就选他的吧，毕竟他先想到了这个点子...我只是太蠢了，没看出来他也有同样的想法。 - LiKao

Answer 4

int edgeCb( graphPT g, int x, int y )
{
    if ( dist[ y ] > dist[ x ] + 1 ) {
        dist[ y ] = dist[ x ] + 1; // New way
        ways[ y ] = ways[ x ]; // As many ways as it's parent can be reached
    } else if ( dist[ y ] == dist[ x ] + 1 ) {
        ways[ y ] += ways[ x ]; // Another way
    } else {
        // We already found a way and that is the best
        assert( dist[ y ] < g->nv );
    }
    return 1;
}

上述代码可以为本文提到的所有类型的图形提供正确的结果。基本上，这是BFS遍历的边回调函数。

dist [ start ] = 0; ways [ start ] = 1;

对于其他所有顶点 dist [ x ] = numberOfVertices; // 这超出了最大可能的距离

BFS ( g，start ) ;

如果 ways [ end ] 不为零，则表示该数为路径数量，而 dist [ end ] 表示最短距离。

如果 ways [ end ] == 0，则意味着无法从起点到达终点。

请告诉我是否存在任何漏洞。

- vamsi

Answer 5

我觉得这个算法看起来是正确的。

如你所知，BFS是一种线性时间（O(N)）搜索，因为完成它所需的时间 T 最坏情况下为 T = C + a * N，其中 N 是节点数，C 和 a 是任何固定的常数。

在你的情况下，进行两次搜索 - 首先从 v 到 w，然后从 w 到 v - 的最坏情况是 2T 或者 2C + 2a * N，如果定义一个新的 C' = 2C 和一个新的 a' = 2a，因为 C' 和 a' 都是固定常数，所以仍然满足线性时间要求 O(N)。

- Dan Nissenbaum

---

谢谢。一个问题：在图问题中，线性时间也意味着O(n)吗？不仅仅是一次性完成所有事情？ - Jackson Tale

@JacksonTale 通常在任何算法中都意味着O(n)。但在图形算法中有一个问题：n可以表示顶点或边的数量。 - soulcheck

Dan，抱歉取消了你的答案标记为正确的状态。qrqrq发现了我的算法中的一个缺陷。 - Jackson Tale

我没有详细说明你将使用的BFS算法的性质，而是专注于线性时间问题。我相信BFS算法的一个版本足以避免多次递归，因此保持BFS算法的O（N）特性，避免指数递归。请参见我的上面的评论。我还没有编写它进行测试，但我认为它应该可以工作。 - Dan Nissenbaum

Answer 6

通过改变BFS来实现最简单的解决方案：

count(v) = 0，count(s) = 1。对于v的每个邻居u，如果(d(v) + 1 == d(u))，则count(u) += count(v)。现在重置所有内容并从结束顶点执行相同操作。

- Ilan Aizelman WS

Answer 7

请看这里给出的好解释：

https://www.geeksforgeeks.org/number-shortest-paths-unweighted-directed-graph/

简而言之，我们可以修改任何最短路径算法，在更新步骤时增加一个计数器，用于记录当前路径提案与此前发现的最短路径长度相同的最短路径数量。

在特定情况下，当图是无权图或所有边的权重都相同时，最简单的方法是修改 BFS 算法。

- Jonathan Prieto-Cubides

Answer 8

我可以这样做吗？

1. 我使用BFS遍历，直到到达目标顶点并维护级别
2. 一旦到达目标级别，我使用以下级别表

从级别表开始，我开始向后遍历，在我们的路径中计算到顶点的父节点数（第一次是目标顶点）。
在每个步骤中，我将在特定级别找到的不同父节点数乘以我可以到达目标顶点的最短路径。
我向上移动级别，只考虑落入我的路径的节点，并在每个级别上找到的不同父节点数相乘，直到达到级别0。

这个方法可行吗？

- Rahul Krishna