所以我们看到有些DAG在它们的一些顶点之间有2n-2个不同的路径;这是一个黯淡的前景，因为根据权重和你选择 d ，你可能不得不考虑所有 . 这本身并不能有效地选择某种形式的最佳（这是你正在寻找的） .
编辑：好的，这就是我要做的事情：
删除权重为0的所有边（更小，但是你已经排除了），因为它们永远不能满足你的第二个标准 .
做图的拓扑排序;在下面，让's only consider the part of the topological sorting of the graph from s to e, let'调用整数区间[s; e] . 删除图表中的所有内容，也可以查看是否存在从s到e的路径，因此您将知道是否存在任何路径s -...-> e . 该部分的复杂性为O（n m） .
现在，这给你的空间复杂度为O（n ^ 3），时间复杂度为O（n²m） - 数组有O（n²）项，我们必须迭代O（m）数组，每个边有一个数组 - 但我认为's very obvious where the wasteful use of data structures here can be optimized using hashing structures and other things than arrays. Or you could just use a one-dimensional array and only store the current minimum instead of recomputing it every time (you' ll必须将路径边缘权重的总和与前任顶点封装起来，因为你需要知道重建路径的前任），这会将数组的大小从n²改为n，因为你现在每个路径到顶点的节点数只需要一个条目，将算法的空间复杂度降低到O（n²），时间复杂度降低到O（nm） . 你也可以尝试做一些形式的拓扑排序，摆脱你无法达到的顶点 e ，因为那些也可以安全地被忽略 .
1 回答
无论你最终做什么，首先从
s开始做一个BFS / DFS，看看是否甚至可以达到e;这只需要你O（n m）所以它不会增加问题的复杂性（因为你需要查看所有的顶点和边缘） . 此外，在执行任何其他操作之前删除所有带有权重0的边缘，因为这些边缘永远不会满足您的第二个标准 .编辑：我想出了一个算法;这是多项式，但根据图表的大小，它可能仍然不够高效 . 请进一步查看编辑 .
现在有一些复杂性 . 这里要考虑的第一件事是我们可以实际拥有多少路径的上限，因此根据
d的选择和边的权重，我们还有任何潜在算法的复杂性的上限 .DAG中可以有多少条边？答案是
n(n-1)/2，这是一个紧束缚：取n顶点，从1到n的顺序排序;对于两个顶点i和j，将边i->j添加到图iffi<j. 这总计为n(n-1)/2，因为这样，对于每对顶点，它们之间只有一条有向边，这意味着图中的边数与我们在n顶点上的完整无向图中的边数一样多 .在上面描述的图中，从一个顶点到另一个顶点可以有多少条路径？答案是2n-2 . 归纳证明：
如上所述，将图形放在2个顶点上;从顶点1到顶点2有1 = 20 = 22-2路径：（1-> 2） .
归纳步骤：假设从顶点开始有2n-2条路径，如上所述的
n顶点图形的数字1到具有数字n的顶点，增加每个顶点的数量并添加新的顶点1以及所需的n边缘 . 它有自己的边缘到现在标记为n+1的顶点 . 此外，对于[2; n]中的每个i，它具有到该顶点的2i-2个路径（它具有其他顶点共同具有顶点的所有路径n+1，每个"prefixed"具有边缘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个不同的路径;这是一个黯淡的前景，因为根据权重和你选择
d，你可能不得不考虑所有 . 这本身并不能有效地选择某种形式的最佳（这是你正在寻找的） .编辑：好的，这就是我要做的事情：
删除权重为0的所有边（更小，但是你已经排除了），因为它们永远不能满足你的第二个标准 .
做图的拓扑排序;在下面，让's only consider the part of the topological sorting of the graph from s to e, let'调用整数区间[s; e] . 删除图表中的所有内容，也可以查看是否存在从s到e的路径，因此您将知道是否存在任何路径s -...-> e . 该部分的复杂性为O（n m） .
现在的实际算法：
按拓扑排序所强加的顺序遍历[s; e]的顶点
对于每个顶点v，存储二维数组信息;让我们称之为prev [] []，因为它将存储有关通向它的路径上的节点的前驱者的信息
在prev [i] [j]中
，如果j是该路径上当前顶点的前身，则存储长度的总路径（在顶点中计数）i作为边缘权重之和的多长时间 . 例如，pres 1 [1] [s]将具有边缘s-> s 1的权重，而pres 1中的所有其他条目将为0 / undefined .
计算新数组时顶点v，我们所要做的就是检查它的入射边缘并在数组上迭代这些边缘的起始顶点 . 例如，假设顶点v具有来自顶点w的入射边缘，具有权重c . 考虑一下prev [i] [w]应该是什么 . 我们有一个边缘w-> v，所以我们需要在v中设置prev [i] [w]
min（prew [i-1] [k]表示所有k，但忽略带0的条目c）（注意数组的下标！）;我们有效地采用了导致w的长度为i-1的路径的成本，并且增加了边缘的成本w-> v . 为什么最低？对于长度为i-1的路径，顶点w可以有许多前驱;但是，我们希望保持低于成本限制，每个顶点的贪婪最小化将为我们做 . 我们需要在[1; s-v]中为所有我做这个 .
在计算顶点的数组时，不要设置会为您提供成本高于d的路径的条目;由于所有边都具有正权重，因此我们只能通过每条边获得更昂贵的路径，因此请忽略它们 .
一旦你到达e并完成了计算pree，你就完成了这部分算法 .
从pree [e-s]开始迭代pree;由于我们没有循环，所有路径都是简单的路径，因此从s到e的最长路径可以有e-s边缘 . 找到最大的i，使得pree [i]具有非零（意味着它被定义）条目;如果不存在，则没有符合您标准的路径 . 您可以使用其他顶点的数组重建任何现有路径 .
现在，这给你的空间复杂度为O（n ^ 3），时间复杂度为O（n²m） - 数组有O（n²）项，我们必须迭代O（m）数组，每个边有一个数组 - 但我认为's very obvious where the wasteful use of data structures here can be optimized using hashing structures and other things than arrays. Or you could just use a one-dimensional array and only store the current minimum instead of recomputing it every time (you' ll必须将路径边缘权重的总和与前任顶点封装起来，因为你需要知道重建路径的前任），这会将数组的大小从n²改为n，因为你现在每个路径到顶点的节点数只需要一个条目，将算法的空间复杂度降低到O（n²），时间复杂度降低到O（nm） . 你也可以尝试做一些形式的拓扑排序，摆脱你无法达到的顶点
e，因为那些也可以安全地被忽略 .