28

这是练习：

设 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到 w 的最短路径的信息
  6. 第一次在旅行中遇到 w 时，我将 分配global level给shortest leveland count++;
  7. 只要global level等于shortest level，我count每次再次遇到 w 时都会增加。
  8. 如果global level变得大于shortest level，我终止旅行，因为我正在寻找最短路径而不是路径。
  9. 然后我再次为 w 做 2 - 8 到 v

我的算法正确吗？如果我对 w 做 v，然后对 v 做 w，那仍然被认为是线性时间吗？

4

8 回答 8

24

以下是对此的一些想法。

  • 从 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.
于 2012-04-19T13:51:11.093 回答
10

您的算法在图表上中断，例如

  *   *   *   1
 / \ / \ / \ / \
v   *   *   *   w
 \ / \ / \ / \ /
  *   *   *   2

所有边缘从左到右。它计算了两条路径，一条通过1，另一条通过2，但两者都1可以2通过v8 条不同的最短路径到达，总共 16 条。

于 2012-04-19T12:13:56.437 回答
4

正如 qrqrq 所示，您的算法在某些图表上失败，但 BFS 的想法很好。相反，维护一个初始化为零z的大小数组；保持到距离小于in|V|的已发现顶点的最短路径数。还要维护一个大小数组，如果该距离小于，则该数组是从到顶点的距离。初始化为 0、0和1（从to有一条长度为 0 的路径），并设置to和to的所有其他条目。ilevelz[i]d|V|d[i]vilevelleveld[v]z[v]vvd-1z0

现在，每当您在 BFS 中遇到从ito的边缘时，然后：j

  • 如果d[j] = -1，则设置d[j] := level和z[j] := z[i]。
  • 如果d[j] = level，则设置z[j] := z[j] + z[i]。
  • 否则，什么也不做。

原因是对于每条从到的最短路径，都有一条从v到的i最短路径。这将给出从线性时间到每个顶点的最短路径数。现在再次执行相同操作，但从.vjvw

于 2012-04-19T13:05:36.183 回答
2

这个算法对我来说看起来是正确的。

如您所知，BFS 是O(N)一个T线性时间(T = C + a * NNCa

在您的情况下，执行两次搜索 - 首先是 from vto w，然后是 from wto v- 是（最坏的情况）2T或，如果您定义一个 new和一个 new 2C + 2a * N，这也满足线性时间要求，因为两者和也是固定常数.O(N)C' = 2Ca' = 2aC'a'

于 2012-04-19T11:09:04.497 回答
2 
int edgeCb( graphPT g, int x, int y )
{
    if ( dist[ y ] > dist[ x ] + 1 ) {
        dist[ y ] = dist[ x ] + 1; // New way
        ways[ y ] = ways[ x ]; // As many ways as it's parent can be reached
    } else if ( dist[ y ] == dist[ x ] + 1 ) {
        ways[ y ] += ways[ x ]; // Another way
    } else {
        // We already found a way and that is the best
        assert( dist[ y ] < g->nv );
    }
    return 1;
}

上面的代码为我在这篇文章中提到的所有类型的图表提供了正确的结果。基本上它是 BFS 遍历的边缘回调。

距离 [ 开始 ] = 0; 方式[开始] = 1；

其余所有顶点 dist[ x ] = numberOfVertices; // 这超出了最大可能距离

BFS（克，开始）；

如果ways[end] 不为零，则表示路径数，dist[end] 表示最短距离。

Incaseways[ end ] == 0 意味着 end 不能从 start 到达。

请让我知道这是否有任何循环漏洞。

于 2015-01-13T03:17:02.507 回答
2

通过更改 BFS 最简单的解决方案：

count(v) = 0，count(s) = 1。对于 v 的每个邻居 u，如果 (d(v) + 1 == d(u))，则 count(u) += count(v)。现在重置所有内容并从末端顶点执行相同操作。

于 2017-07-27T07:20:56.857 回答
0

我可以这样做吗

  1. 我使用 BFS 遍历，直到到达目标顶点并保持水平
  2. 到达目标级别后，我使用级别表如下

从级别表中，我开始遍历计算路径中顶点的父节点数量（第一次它将是目标顶点）。
在每一步，我都会将在该特定级别找到的不同父节点的数量乘以到目标顶点的最短路径。
我向上移动级别，只考虑落入我的路径的节点，并将在每个级别找到的不同父级的数量相乘，直到达到级别 0。

这行得通吗？

于 2014-09-17T17:55:10.663 回答
0

只需检查此处给出的良好解释：

https://www.geeksforgeeks.org/number-shortest-paths-unweighted-directed-graph/

简而言之，我们可以修改任何最短路径算法，当更新步骤到来时，当当前路径提议与直到那一刻发现的最短路径长度相同时，增加一个计数器，用于计算先前发现的最短路径的数量。

在特定情况下，当它是未加权的图或所有边的权重恒定时，最简单的方法是修改 BFS。

于 2018-10-13T20:55:18.867 回答