带约束的有向无环加权图的遍历
有效的解决方案路由的约束是：
- 考虑到第二个约束，路由中遍历的所有边的权重之和必须是图中可能的最高值。
- 所选路由中必须访问过N个顶点（包括起始和结束顶点）。
通常，图形将有大量的顶点和边，所以尝试所有的可能性是不可能的，需要相当有效的算法。
共有1个答案
我不确定你是对图中任何长度为N的路径感兴趣，还是只对两个特定顶点之间的路径感兴趣；我怀疑是后者，但你在问题中没有提到这一限制。
如果是前者，解决方案应该是一个简单的类似Dijkstra的算法，在该算法中，您可以根据潜在路径值对所有边缘进行排序，该值从边缘权重开始，并通过已经构建的邻近路径进行调整。在每次迭代中，取具有最佳潜在路径值的节点，并将其添加到一个附加路径中。当你得到一条长度为N的路径（或你在两侧切断的更长的路径）时停止。还有一些其他的技术细节。WRT.创建长路径，但我不会详细说明，因为我怀疑这不是您感兴趣的。-）
如果您有固定的source和sink，我认为这并不涉及深度魔法--只需运行一个基本的Dijkstra，其中路径将与添加到队列中的每个顶点相关联，但不要将路径长度>=N的顶点插入队列，除非其路径长度为N，否则不要将sink插入队列。
-
输入： 生成的树： 输出： 规则： < li >输入代码总是会产生一个有向无环图 < li >每个节点都有一些wait_time值 < li >完整的图形遍历应该计算整个图形的总等待时间 < li >必须并行遍历所有独立节点(或者至少时间计算应该是这样) < li >如果两个不同节点的wait_time发生重叠，则将考虑最大值，遍历时间较短的节点将移动到下一个独立节点 < li >除了根和叶(可以
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我的视图控制器中有几个视图，当检测到向上滑动时向上移动，然后当检测到向下滑动时向下移动。我使用CGRectOffset通过调整y原点来强制视图移动。我现在使用IB对视图施加了约束，我不确定移动视图的最佳方法是什么，以便它们最终在iPhone 5、6和6上的正确位置。 目前我正在做这样的事情： 用比值改变常数是否更好？因此，对于上面的约束，不使用338，这样做是否更好:
-
这将使约束在范围内，为提供额外的参数。这里我的意图是包含一些（隐藏的）具体类型，它应该用作多态函数GHC compulins的具体类型： 我的用例的假设是1。同时计算和2。隐藏类型的值涉及（至少部分）第一个元组元素的计算。这意味着我不想在中调用两次（一次是获取，一次是使用该类型绑定第一个元组元素）。在存在约束的情况下，是否有某种方法使的定义成为可能？
-
我能够使用这个算法在一个加权DAG中找到最长的路径（使用拓扑排序，然后放松每个边）。我现在的问题是，是否有一个算法来找到DAG的前3个最长的路径？或者，有没有实现这种算法的javascript或java库？
-
我想知道什么是实现无向加权图的有效方法。我想在上面执行Prims和Kruskal算法。我知道邻接列表，但这不会浪费内存；为。假设我有两个顶点A和B，由权重为“x”的边连接，所以我需要在邻接列表中添加两个条目： 我是不是漏掉了什么？