问题标签 [longest-path]

我正在考虑如何在一个完整的有向图中为每个顶点找到一条最长的路径。 此类图表的示例

因此，对于每个单个顶点，我想找到一个可以通过的最大可能顶点数量（不超过一次通过任何顶点）以及具有该特定长度的特定路径。

例如在给定的图中，对于起始顶点 nr.1，最大长度为 4，路径：1,4,2,3 或 1,2,3,4（我只需要获取其中一个，而不是全部）。

什么样的算法可以处理？

以防万一，我使用 C++。

正如标题所说，我必须在有向图中找到最长的路径，其中每个节点最多有两个传入边和两个传出边。我不知道这个事实是否有帮助。该图最多有 10000 个节点。我需要找到从节点 0 到节点“退出”的最长路径，即 10001。

我尝试编写 dijkstra 代码，但没有成功。

提前致谢。

我们能否转换有向加权图，使其从指定源到目的地的每条路径都具有相同的成本？每条路径的成本应该等于原始图中的最大成本路径。如何将任何有向加权图转换为这种类型的图？是否可以将每个有向加权图转换为这种类型的图？

图的来源和目的地是预定义的。

我想使用 Floyd-warshall 算法找到加权无向图的任意两个顶点之间的最大距离。为此，我做了一些更改：

1. 我添加负权重而不是正数。

2. 然后我找出最短路径。

但它没有给我正确的输出。有人可以指出我正在犯的错误。

相同的输入是：-

1[测试用例数]

5 4 [节点数，边数]

1 2 4 [第一个节点，第二个节点，权重]

3 2 3 [第一个节点，第二个节点，权重]

2 5 2 [第一个节点，第二个节点，权重]

4 1 1 [第一个节点，第二个节点，权重]

我想在有向（非循环）图中找到最长的路径。假设我知道起始节点 - 接收器。路径应该从这一点开始。我在想我可以将边的权重设置为-1。有很多方法可以找到所有最短路径，但你必须通过终点。是否有可能获得最短路径（无论结束节点）？

假设我想找到节点 nr 1（接收器）的最长路径。所以这个算法应该给我1-2-3-4-5-6。

我知道找到最长的路径是一个 NP Hard 问题。

我们要求我们改变 Dijkstra 的算法，通过在算法中添加另一个参数来找到最长的路径。一个参数，如从源到给定顶点的距离、顶点的前任、后继、边数……例如，我们可以根据最大距离以外的参数从队列中提取顶点，或者我们可以另一个队列...

我们首先要做的是改变初始化，使除了源节点之外的所有顶点距离 = 0，即 = 无穷大。然后我们从顶点队列中提取距离最大的顶点。然后，我们反转松弛符号，这样如果顶点大于当前距离，则保存距离。

我可以添加什么参数来提高 Dijkstra 在查找最长路径时的性能？它不必在 100% 的时间内工作。

这是 Dijkstra 的算法：

这是我们的修改版本：

我想获得两个节点之间的最长路径。

我有带有 id 的车站 这些车站与 oder 车站相连。关系是“出租车”、“公共汽车”、“船”。

那么我如何获得整体最长的路径？（或最长最短路径）我不想要特定节点的最长路径。

我尝试了多个查询，但通常我只得到“内部错误......”

这是从我的图表中截取的（这里是最短路径）： 在我的脑海中，我认为我必须找到所有节点的所有最短路径，然后返回最长的最短路径。但我没有在查询中得到它

我试图在具有连续数字的矩阵中找到最长的路径，从而给出正确的答案。函数调用递归执行，直到附近没有连续的数字，并且每次检查单元格是否被访问

但是当我尝试相同的代码来查找二进制矩阵中的最长路径时，程序停止执行

这段代码有什么错误。在此先感谢

我正在研究一种图聚类算法，该算法要求我为无向图中的所有顶点对 u, v 找到一个值 R(u, v)。

因此，在这里，R(u, v) 是通过在从 u 到 v 的所有简单路径上找到最大值来计算的。函数 f(u, v) 是已知的并且没有我们可以使用的特殊属性。

我正在阅读这可以有效地使用二项式堆来完成，而无需实际枚举 u 和 v 之间的所有简单路径。

有人可以指导我如何解决这个问题吗？谢谢。

我已经完成了自己的研究，但是我找不到适合我需求的解决方案。

问题是，我有一辆卡车需要花费它的负载（比如说垃圾）。有 city(node) 和 edges(way) 可以是正边或负边。虽然卡车采取一种方式，但它可能会松动或必须获得更多（浪费）取决于所选方式（边缘）。如果它选择了正边沿，它会丢失与选择的方式值完全相同的浪费量。反之亦然。

因此，卡车司机必须走一定的步数（无论边缘的值如何，每一步都需要一个恒定的时间）并且司机有有限的时间回到他的家（原点）（时间将是一个给定的参数）

所以在这个图中，我们有节点，我们有一个方向的边，这条边可以有负值或正值，并且在图中可以有允许驱动程序使用或不使用的循环。并且节点可以用不同的边相互指向。（从 A 到 B 边缘 val 是 5 ）（从 B 到 A 边缘 val 是 -3 等等..）

所以我想给司机最好的办法，在最短的时间内用尽最大的负荷。

所以，问题是这样的。

我想要的是，注意实际的代码。

如果您知道可以指定的问题的名称，不客气。如果您想用伪代码或文字分享您自己的算法。也欢迎你。如果您想分享一个您认为有类似问题的链接。也欢迎你。

如果您认为无法解决。请分享您的想法或证明的链接。

提前致谢。