如何找到的不同的最短路径的数目两个顶点之间，在向图和与线性时间？ [英] 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. ，它要求的不同的最短路径的数量。首先，路径应是最短的，则可能有不止一个这样的最短路径的长度是相同的。
V和W的
3. ，所以无论是从v到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. 我保持一个计数的最短路径数
3. 我想首先使用BFS从V，也保持了全球信息
4. 我增加了全球由一个每次都那么BFS达到一个新的水平
5. 在我还保持最短路径最短电信息为w
6. 在我第一次见面在旅途中W，我给你的全球到最短电和计数++ ;
7. 只要全球等于给最短电，我增加计数每次我遇到W¯¯又一次。
8. 如果在全球变得大于最短电，我结束了旅行，因为我要找最短路径而不是路径。
9. 然后我做2 - 8再次用W到V

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和则w到v，是仍然被视为线性时间？

---

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->多个最短路径瓦特通过节点x，或者如果有多个路径成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已经遇到过，可以遵循所有路径将低于previous最短路径中的至少一个更长的时间。因此没有这些路径可以向的总和。

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 usuall with BFS.
 - Instead of adding just nodes to the queue in the DFS add nodes plus number of incomming 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 noded
 - when you encounter the final, the number that is stored with it, is the number of possible paths.

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