1. 首页
  2. 问题
  3. 如何在有向图和线性时间中找到两个顶点之间不同的最短路径的数量？
一尘不染

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

algorithm

这是练习：

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

对于此消费税，我总结如下：

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

从以上几点来看，我有以下想法：

  1. 我不需要使用Dijkstra的算法，因为该图未加权，我们正在尝试查找所有最短路径，而不仅仅是单个路径。
  2. 我count为最短路径数保持
  3. 我想先使用v的BFS并维护global level信息
  4. global level每次我将BFS 增加一倍
  5. 我还维护了shortest level最短路径的信息
  6. 旅行时第一次遇到w时，我将分配global level给shortest level和count++；
  7. 只要global level等于shortest level，我count每次再遇到w都会增加。
  8. 如果global level变得大于shortest level，则我终止行程，因为我在寻找最短路径而不是路径。
  9. 然后我再次对w到v做2-8

我的算法正确吗？如果我对v进行v运算，然后对w进行v运算，那是否仍视为线性时间？


阅读 487

收藏
2020-07-28

共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.
2020-07-28