如何在有向图和线性时间图中求出两个顶点之间的不同最短路径数？

Question

下面是练习：

设v和w是有向图G= (V，E)中的两个顶点。设计一种线性时间算法，以求v和w之间不同的最短路径(不一定顶点不相交)的数目。注意:G中的边是不加权的。

关于这部分工作，我的摘要如下：

1. 它是一个有向图
2. 它要求不同最短路径的数目。首先，路径应该是最短的，然后可能有多个这样的最短路径，其长度是相同的。
3. 在v和w之间，所以从v到w和从w到v都应该计算在内。
4. 线性时间。
5. 图是不加权的。

根据以上各点，我有以下想法：

1. 我不需要使用迪克斯特拉算法，因为图是不加权的，我们试图找到所有最短的路径，而不仅仅是单一的路径。
2. 我为最短路径数维护一个count
3. 我想首先使用BFS，并维护global level信息。
4. 我每次增加一个global level，BFS就达到一个新的水平。
5. 我还维护了最短路径到w的shortest level信息。
6. 当我第一次旅行的时候，我把global level分配给shortest level和count++；
7. 只要global level等于shortest level，我每次见到w时都会增加count。
8. 如果global level变得比shortest level大，我就终止旅行，因为我在寻找最短路径而不是路径。
9. 然后我对w到v再做2-8次。

我的算法正确吗？如果我做v到w，然后w到v，那么它仍然被认为是线性时间吗？

Answer 1

这里有一些关于这方面的想法。

• 从v->w到节点x只能有多条最短路径，如果通过相同的顶点有多条路径进入x，或者在同一DFS级别上多次遇到x。

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

如果以前遇到过x，则当前路径中没有一条能够对另一条最短路径作出贡献。由于以前遇到过x，所以所有可以遵循的路径至少比前面的最短路径长一条。因此，所有这些路径都不能对和作出贡献。

这意味着，我们最多只能遇到每一个节点并完成。所以正常的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.

Answer 2

您的算法在一个图上崩溃，如

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

所有的边缘都从左到右。它计算两条路径，一条通过1，另一条通过2，但从v可以通过八条不同的最短路径到达1和2，总共16条。

Answer 3

正如qrqrq所示，您的算法在一些图上失败了，但是BFS的思想是好的。相反，维护一个大小为z的数组|V|，将其初始化为零；将到达已发现顶点i的最短路径数保持在z[i]中的level的距离以内。还维护一个大小为d的数组|V|，这样，如果距离小于level，则d[i]是从v到顶点i的距离。将level初始化为0，将d[v]初始化为0，将z[v]初始化为1(从v到v有一个长度为0的路径)，并将d的所有其他条目设置为-1，将z的条目设置为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开始。