如何在有向图中和线性时间中找到两个顶点之间的不同最短路径的数量? [英] How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

问题描述

这是练习:

设 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:

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

1. It is a directed graph
2. It asks for the number of different shortest paths. First, the paths should be shortest, then there might be more than one such shortest paths whose length are the same.
3. between v and w, so both from v to w and from w to v should be counted.
4. linear-time.
5. The graph is not weighted.

<小时>

从以上几点，我有以下几点思考:

---

From the points above, I have the following thoughts:

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

1. I don't need to use Dijkstra’s Algorithm because the graph is not weighted and we are try to find all shortest paths, not just single one.
2. I maintain a count for the number of shortest paths
3. I would like to use BFS from v first and also maintain a global level information
4. I increase the global level by one each time then BFS reaches a new level
5. I also maintain the shortest level info for shortest path to w
6. The first time I meet w while traveling, I assign the global level to the shortest level and count++;
7. as long as the global level equals to the shortest level, I increase count each time I met w again.
8. if the global level becomes bigger than the shortest level, I terminate the travelling, because I am looking for shortest path not path.
9. Then I do 2 - 8 again for w to v

<小时>

我的算法正确吗?如果我对 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.

这篇关于如何在有向图中和线性时间中找到两个顶点之间的不同最短路径的数量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！