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

Question

这是练习:

Let v and w be two vertices in a directed graph G = (V, E). Design a linear-time algorithm to find the number of different shortest paths (not necessarily vertex disjoint) between v and w. Note: the edges in G are unweighted

---

对于这个excise，我总结如下:

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

---

从以上几点，我有以下几点想法:

1. 我不需要使用 Dijkstra’s Algorithm因为该图没有加权，我们试图找到所有最短路径，而不仅仅是一条。
2. 我为最短路径的数量维护了一个count
3. 我想首先使用来自 v 的 BFS，同时维护一个全局级别信息
4. 我每次将全局级别增加一个，然后BFS达到一个新的级别
5. 我还维护到 w 的最短路径的 shortest level 信息
6. 旅行中第一次遇到w，我将全局级别分配给最短级别和count++；
7. 只要global level等于shortest level，每次遇到w我都会增加count。
8. 如果 global level 变得比 shortest level 大，我终止旅行，因为我正在寻找最短路径而不是路径。
9. 然后我再做 2 - 8 w 到 v

---

我的算法正确吗？如果我对 w 执行 v，然后对 v 执行 w，这仍然被视为线性时间吗？

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.