首页 文章

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

提问于
浏览 次
24

这是练习：

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

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

  • 这是一个有向图

  • 它要求 the number of different shortest paths . 首先，路径应该是最短的，然后可能存在不止一条这样的最短路径，其长度相同 .
    在v和w之间

  • ，因此应该计算v到w和w到v .

  • 线性时间 .

  • 图表未加权 .

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

  • 我不需要使用Dijkstra’s Algorithm，因为图表没有加权，我们试图找到所有最短路径，而不仅仅是单个路径 .

  • 我为最短路径的数量维持了 count

  • 我想先从v使用BFS并保留 global level 信息

  • 我每次增加 global level ，然后BFS达到一个新的水平

  • 我还保留 shortest level 信息，以获取最短路径

  • 我第一次在旅行时遇到w，我将 global level 分配给 shortest level 和 count++ ;

  • 只要 global level 等于 shortest level ，每次遇到w时我都会增加 count .

  • 如果 global level 变得比 shortest level 大，我终止了旅行，因为我正在寻找最短的路径而不是路径 .

  • 然后我再次做2到8，对于w

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

algorithm data-structures graph breadth-first-search

8 回答

  • 0

    以下是对此的一些想法 .

    • 从v-> w到节点x只能存在多条最短路径，如果通过相同的顶点有多条路径进入x，或者在同一DFS级别多次遇到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.
    回复于
  • 9

    你的算法在图表上打破了

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

    所有边缘从左向右指向 . 它计算两条路径，一条通过 1 ，另一条通过 2 ，但是 1 和 2 都可以通过八条不同的最短路径从 v 到达，总共十六条 .

    回复于
  • 0

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

    现在，只要您在BFS中遇到 i 到 j 的边缘，那么：

    • 如果 d[j] = -1 ，则设置 d[j] := level 和 z[j] := z[i] .

    • 如果 d[j] = level ，则设置 z[j] := z[j] + z[i] .

    • 否则，什么都不做 .

    原因是对于从 v 到 i 的每条最短路径，从 v 到 j 有一条最短路径 . 这将给出从线性时间内 v 到每个顶点的最短路径数 . 现在再次这样做，但从 w 开始 .

    回复于
  • 2

    这个算法对我来说是正确的 .

    如你所知，BFS是一个线性时间（ O(N) ）搜索因为时间 T 在最坏的情况下，完成它需要 T = C + a * N ，其中 N 是节点数， C ， a 是任何固定常量 .

    在您的情况下，执行两次搜索 - 首先从 v 到 w ，然后从 w 再到 v - 是（最差） 2T 或 2C + 2a * N ，如果您定义新的 C' = 2C ，则还满足线性时间要求 O(N) a' = 2a ，因为 C' 和 a' 都是固定常量 .

    回复于
  • 19
    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遍历的边缘回调 .

    dist [start] = 0;方式[开始] = 1;

    休息所有顶点dist [x] = numberOfVertices; //这超出了可能的最大限度

    BFS（g，start）;

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

    Incase方式[end] == 0表示从头开始无法到达终点 .

    如果这里有任何环洞，请告诉我 .

    回复于
  • 4

    Simplest solution by changing BFS:

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

    回复于
  • 2

    我能这样做吗？

    • 我使用BFS遍历，直到到达目标顶点并保持水平

    • 一旦我到达目的地级别，我使用级别表如下

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

    这有用吗？

    回复于
  • 2

    请检查一下这里给出的好解释：

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

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

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

    回复于

相关问题