程序员经验分享-hwhale

DAG 中两个节点之间的路径数

2024-04-27

我想找到 DAG 中两个节点之间的路径数。 O(V^2) 和 O(V+E) 是可以接受的。

O(V+E) 提醒我以某种方式使用 BFS 或 DFS，但我不知道如何使用。 有人可以帮忙吗？


对 DAG 进行拓扑排序，然后从目标向后扫描顶点到源。对于每个顶点v，记录来自的路径数v到目标。当你到达源头时，该计数的值就是答案。那是O(V+E).

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

graphtheory

directedacyclicgraphs

DAG 中两个节点之间的路径数 的相关文章

  • 在 O(nloglogn) 最坏情况时间内对具有 O(logn) 个不同元素的 n 元素数组进行排序

    目前的问题是标题本身的内容 即给出一种算法 该算法在 O log logn 最坏情况时间内对具有 O log n 个不同元素的 n 元素数组进行排序 有任何想法吗 此外 您通常如何处理具有多个非不同元素的数组 O 日志 日志 n 时间足以让

  • 分割如何提高埃拉托斯特尼筛法的运行时间？

    我遇到了埃拉托色尼筛的分段实现 它的运行速度比传统版本快很多倍 有人可以解释一下分段如何提高运行时间吗 请注意 我想在其中找到素数 1 b 它适用于这个想法 用于查找 10 9 之前的质数 我们首先生成 sqrt 10 9 以下的筛选素数

  • 如何读取未知数量的输入？

    我正在使用 C Primer 这本书学习 C In 第1 4 3节 给出了以下关于读取未知数量的输入的示例代码 include

  • 对 Big O 表示法仍然有点困惑

    所以我一直在尽力理解 Big O 表示法 但仍然有一些事情我感到困惑 所以我一直读到如果某件事是 O n 那么它usually指的是算法的最坏情况 但它不一定要指最坏的情况 这就是为什么我们可以说插入排序的最佳情况是 O n 但是 我无法真

  • 天气预报算法多样

    目前 英国气象局的预测引发了一场巨大的 风暴 他们预测冬季将是温和 潮湿的冬季 而北爱尔兰的气温却是有记录以来最冷的 地面上有厚厚的积雪 这在 12 月通常很少见 这是我很想尝试的东西 并不是我声称我可以击败他们 而是想知道人们目前正在使用

  • 算法的最佳、最差和平均情况运行时间是多少？

    算法的最佳 最差和平均情况运行时间是多少 用最简单的术语来说 对于输入大小为n 最好的情况 最快完成时间 选择最佳输入 例如 排序算法的最佳情况是已经排序的数据 最坏的情况下 完成最慢的时间 选择了消极的输入 例如 排序算法的最坏情况可能是

  • 贪心算法的使用示例？

    贪心算法有什么用 一个真实的例子 最小生成树 Prim http en wikipedia org wiki Prim s algorithm的算法和克鲁斯卡尔的 http en wikipedia org wiki Kruskal s a

  • 树中的节点是否被视为其自己的祖先？

    我想知道计算机科学背景下对 祖先 定义的共识是什么 我问只是因为在算法简介 http en wikipedia org wiki Introduction to Algorithms 第二版 第 14 页 第259章 有算法的描述Tree

  • 比较周期性数据的快速方法

    假设我有任意类型的数据集 A B C D 并且我想将其与另一个数据集进行比较 我希望 A B C D B C D A C D A B 和 D A B C 的比较成立 但是不适用于 A C B D 或任何其他未类似排序的集合 有什么快速方法可

  • 如何使用哈希表在最小堆上实现 O(1) 删除

    在某处阅读以下声明 可以使用附加的哈希表来快速删除 最小堆 问题 gt 如何组合priority queue and unordered map这样我就可以实现上面的想法了 include

  • 在 Python 中删除表达式树及其每个子表达式树中第一个元素周围的括号

    目标是实现简化操作 删除表达式树及其每个子表达式树中第一个元素周围的括号 其中表达式作为括在各个括号中的字符串输入给出 这必须适用于任意数量的括号 例如 12 3 45 6 gt 123 45 6 删除 12 周围的括号 然后删除 45 周

  • 用 ruby​​ 解决旅行商问题（50 多个位置）

    我在一家快递公司工作 目前 我们 手动 解决了 50 多个地点的路线 我一直在考虑使用 Google Maps API 来解决这个问题 但我读到有 24 点的限制 目前我们在服务器中使用 Rails 因此我正在考虑使用 ruby 脚本来获取

  • 合并空间上接近的路径/线段的算法

    我正在寻找一种用于街道地图制图概括的几何算法 名称 在我的地图数据中 我有许多路径 点的有序列表 由线段连接 这些路径彼此靠近且几乎平行 我如何 1 识别这些 相邻路径 即如何找到比某个阈值更接近的路径 以及 2 将它们合并成一条路径 即如

  • 优雅的折线“左移”测试

    Given X Y 坐标 即车辆的位置 X Y 数组 它们是折线中的顶点 请注意 折线仅由直线段组成 没有圆弧 我想要的是 计算车辆是在折线的左侧还是右侧 当然还是在顶部 我的做法 迭代所有线段 并计算到每个线段的距离 然后 对于最近的段

  • 给定与总和匹配的长度的唯一 3 位数字 (-1,0,1) 序列的数量

    假设您有一个长度为 n 即空格数 的垂直游戏板 你有一个三面骰子 有以下选项 前进一 停留和后退 如果您低于或高于棋盘游戏空间的数量 则该游戏无效 一旦到达棋盘末端 唯一有效的动作就是 停留 给定确切的骰子投掷次数 t 是否可以通过算法计算

  • Java：使用indexOf方法根据另一个数组对数组进行排序

    我想根据另一个数组 索引 的排序顺序迭代两个数组 A B 在本例中为 10 34 32 21 String A a b c d String B e f g h int indexes 10 34 32 21 为这里的坏例子道歉 我已经更新

  • 为无向无权图实现推重标签算法 s-t 最小割边

    我正在寻找一个好的解决方案来在无向和未加权图中找到 s t 最小切割边 我想使用推送重新标记算法 但我不确定如何实现它以在无向和未加权图上找到最小割 在每对顶点之间有两条反向边 并在所有边上赋予相同的权重 并应用推送重新标记算法 我可以用这

  • 如何在 dijkstra 算法中以 O(log n ) 时间更新优先级队列中的键？

    过去一周我一直在研究 dijkstra 算法 我在 java 中有正确的运行代码 它使用数组来计算标准 findMin 函数 该函数为您提供距离最小的顶点 显然它是 O n 现在我希望使用优先级队列 最小堆 来实现它 我的思考过程是 whi

  • 我想优化这个短循环

    我想优化这个简单的循环 unsigned int i while j 0 j is an unsigned int with a start value of about N 36 000 000 float sub 0 i 1 unsig

  • Bellman-Ford 算法检测什么？负重还是负循环？

    如果给定一个图 现在我们要从源头计算最短路径 现在 如果一条边具有负权重 但在到达目的地时有边到后边返回到该边 我的意思是如果没有循环 那么我们就没有负循环 但是here http en wikipedia org wiki Bellman

随机推荐

热门标签