这是练习:
设 v 和 w 是有向图 G = (V, E) 中的两个顶点.设计一个线性时间算法来找到 v 和 w 之间不同的最短路径(不一定是顶点不相交)的数量.注意:G 中的边是未加权的
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
对于这个消费税,我总结如下:
For this excise, I summarise as follows:
从以上几点,我有以下几点思考:
From the points above, I have the following thoughts:
我的算法正确吗?如果我对 w 做 v 然后对 v 做 w,那仍然被认为是线性时间吗?
Is my algorithm correct? If I do v to w and then w to v, is that still considered as linear-time?
推荐答案这里有一些关于这个的想法.
Here are some ideas on this.
- 从 v->w 到节点 x 只能有多条最短路径,如果有多个路径通过同一个顶点进入 x,或者如果在同一 DFS 级别多次遇到 x.
证明:如果有多个路径通过同一个顶点进入x,显然有多种路径通过x.这很简单.现在让我们假设只有一种方式通过每个顶点进入 x(最多).
Proof: If there are multiple paths entering x through the same vertex there are obviously multiple ways through x. This is simple. Now let us assume there is only one way into x through each vertex going into x (at maximum).
如果之前遇到过 x,则当前路径中没有一条可以促成另一条最短路径.由于之前已经遇到过 x,因此所有可以遵循的路径将至少比之前的最短路径长 1.因此,这些路径都不能对总和做出贡献.
If x has been encountered before, none of the current paths can contribute to another shortest path. Since x has been encountered before, all paths that can follow will be at least one longer than the previous shortest path. Hence none of these paths can contribute to the sum.
然而,这意味着我们最多遇到每个节点一次并完成.所以一个普通的 BFS 就可以了.
This means however we encounter each node at most once and are done. So a normal BFS is just fine.
- 我们甚至不需要知道级别,而是可以在遇到最终节点时获得最终数字.
这个可以编译成一个很简单的算法,主要就是BFS.
This can be compiled into a very simple algorithm, which is mainly just 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.更多推荐
如何在有向图中和线性时间中找到两个顶点之间的不同最短路径的数量?
发布评论