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

Question

这是练习:

令v和w为有向图G =(V,E)中的两个顶点.设计线性时间算法以找到v和w之间的不同最短路径(不一定是顶点不相交)的数量.注意:G中的边缘未加权

---

对于这个消费税,我总结如下:

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

---

从以上几点来看,我有以下想法:

1. 我不需要使用Dijkstra算法,因为图表没有加权,我们试图找到所有最短路径,而不仅仅是单个路径.
2. 我维持一个count最短路径的数量
3. 我想首先使用BFS并保留global level信息
4. 我global level每次增加1,然后BFS达到一个新的水平
5. 我还保留了shortest level最短路径的信息
6. 我第一次在旅途中遇到w,我分配global level给shortest level和count++;
7. 只要global level等于shortest level,我count每次遇到w时都会增加.
8. 如果global level变得比大shortest level,我终止旅行,因为我正在寻找最短的路径而不是路径.
9. 然后我再次做2 - 8对于w

---

我的算法是否正确？如果我做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,但两者1并2可以达到v八个不同的最短路径,共计十六个.