algorithm - 带有限制的加权DAG图中从s到e的路径

Question

考虑具有n节点和m边的有向图。每个边缘都被加权。有一个起始节点s和一个结束节点e。我们想要找到从s到e的路径，该路径具有最大的节点数，使得：



总距离小于某个常数d
从s开始，路径中的每个节点都比前一个节点更靠近节点e。 （例如，在遍历路径时，就剩余路径的边缘权重而言，您将更接近目的地e。）



我们可以假设图中没有周期。没有负权重。解决这个问题的算法已经存在吗？这个问题有名字吗？

Answer 1

无论您最终做什么，都首先从s开始执行BFS / DFS，以查看是否甚至可以达到e；这只需要O（n + m），所以不会增加问题的复杂性（因为无论如何您都需要查看所有顶点和边）。另外，在执行其他任何操作之前，请删除所有权重为0的边缘，因为这些边缘永远不会满足您的第二个条件。

编辑：我想出了一种算法；它是多项式，但是根据图的大小，它可能仍然不够高效。进一步查看编辑内容。



现在有些复杂。在这里首先要考虑的是我们实际上可以拥有多少条路径的上限，因此，根据d的选择和边缘的权重，我们还对任何潜在算法的复杂性都有一个上限。

DAG中可以有多少条边？答案是n(n-1)/2，这是一个严格的界限：取n顶点，将它们从1到n排序；对于两个顶点i和j，将边i->j添加到图iff i<j中。总计为n(n-1)/2，因为这样一来，对于每对顶点，在它们之间恰好有一个有向边，这意味着我们在图中的边缘与在顶点。



在上述图形中，从一个顶点到另一个顶点可以有多少条路径？答案是2n-2。归纳证明：

如上所述，在2个顶点上绘制图形；从顶点1到顶点2的路径为1 = 20 = 22-2（1-> 2）。
归纳步骤：假设从如上所述的n顶点图的编号为1的顶点到编号为n的顶点有2n-2条路径，增加每个顶点的数量并添加一个新的顶点以及必需的n边。它具有自己的顶点边缘，现在标记为1。此外，对于[2; n]中的每个n，它具有2i-2个到该顶点的路径（它具有其他所有顶点到顶点n+1的所有路径，每个路径都以“ i”作为前缀）。这给我们1 +Σnk= 2（2k-2）= 1 +Σn-2k= 0（2k-2）= 1 +（2n-1-1）= 2n-1 = 2（n + 1）-2。



因此，我们看到有些DAG在其某些顶点对之间具有2n-2个不同的路径。前景有些暗淡，因为根据权重和n+1的选择，您可能必须考虑所有因素。但是，这本身并不意味着我们无法有效地选择某种形式的最优（这正是您要寻找的）。



编辑：好的，所以这里我要做什么：


删除权重为0的所有边线（并且更小，但您将其排除在外），因为它们永远无法满足您的第二个条件。
对图进行拓扑排序；在下文中，我们仅考虑从s到e的图的拓扑排序部分，我们称整数间隔[s; e]。从图中删除所有不严格位于该间隔内的内容，这意味着该范围外的所有顶点以及入射边。在topSort期间，您还可以查看是否有一个

从s到e的路径，因此您将知道是否存在任何s -...-> e路径。这部分的复杂度为O（n + m）。
现在实际的算法是：

以拓扑所施加的顺序遍历[s; e]的顶点
分类
对于每个顶点v，存储二维信息数组；叫它吧
prev [] []，因为它将存储有关前辈的信息
通往它的路径上的一个节点
在prev [i] [j]中，存储总路径长度（以
顶点）i是边缘权重的总和，如果j是
该路径上的当前顶点。例如，pres + 1 [1] [s]将具有
边缘s-> s + 1的权重，而pres + 1中的所有其他条目
将为0 /未定义。
在为新顶点v计算数组时，我们要做的就是检查
它的输入边并遍历数组的起始顶点
边缘。例如，假设顶点v从顶点w进入，
有体重c。考虑条目prev [i] [w]应该是什么。
我们有一个边w-> v，因此我们需要将v中的prev [i] [w]设置为
min（prew [i-1] [k]对于所有k，但忽略带有0的项）+ c（注意数组的下标！）；我们有效地承担了
长度为i-1且通向w的路径，并加上边缘w-> v的成本。
为什么最低？顶点w可以具有许多长度路径的前身
我-1;但是，我们希望保持在成本限制以下，以尽量减少贪婪
在每个顶点都会为我们做。我们将需要对[1; s-v]中的所有i执行此操作。
在计算顶点数组时，请勿设置会给您带来麻烦的条目
成本高于d的路径；由于所有边缘都具有正权重，我们只能得到
每个边的路径都比较昂贵，因此请忽略这些路径。
达到e并完成计算pree后，就完成了
算法的一部分。

从pree [e-s]开始迭代pree [e-s];由于我们没有周期，所有
path是简单路径，因此从s到e的最长路径可以具有e-s边。找到最大的
i使pree [i]具有非零（表示已定义）条目；如果不存在，则没有符合您条件的路径。你可以重建
使用其他顶点数组的任何现有路径。


现在，您的空间复杂度为O（n ^ 3），时间复杂度为O（n²m）-数组具有O（n²）项，我们必须遍历O（m）数组，每个边沿一个数组-但是我认为很明显可以使用哈希结构和数组以外的其他东西来优化此处数据结构的浪费。或者，您可以只使用一维数组，仅存储当前最小值，而不是每次都重新计算它（您必须将路径的边缘权重之和与前任顶点一起封装，尽管您需要了解前任顶点来重建路径），这会将数组的大小从n²更改为n，因为您现在每个路径到顶点的节点数只需要一个条目，从而将算法的空间复杂度降低到O （n²）和时间复杂度为O（nm）。您也可以尝试做某种形式的拓扑排序，以摆脱您无法到达1->i的顶点，因为这些顶点也可以安全地忽略。