小度有向无环图中的最短路径
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
共有1个答案
这似乎太好了，不是真的，对不起，如果不是...您可以获得O(n)（编辑:O(n^(4/3)))预处理和O(1)查询。
我认为您知道如何在时间O(n^2)中计算图中所有节点之间的所有最短距离。（这确实是可能的，你似乎知道）
将图形划分为k块，每个块包含n/(5*k)行。（这些块应该在完整的行上开始和结束，并且两个连续的块在各自的第一行和最后一行上重叠）
预处理总时间:O((n/k)^2+k^2)。取k=sqrt(n)，得到O(n)预处理。
查询时间为O(1):取U块末尾的5个节点，V块开头的5个节点（如果块不同），只需比较U->V的25种可能性
编辑
-
给出了一个边上具有任意权的有向无环图和两个特定结点s和t，其中s的内度和t的外度为0。如何确定成本为正的s到t的最短路径？
-
在正加权有向无环图中，我有一个求最短路径的问题，但有最大N步（路径中的边）的限制。假定路径存在。图的另一个性质是，如果边（i,j）在图中，那么对于i 例如，考虑下图。 问题是最多使用k=3步（边）来寻找最短路径。答案是6（路径1->4->5->6)。
-
我在这里要问的问题以前在堆栈溢出中已经被问过了。但我无法正确理解Skiminok发布的解决方案。 这是链接。 我尝试了上面链接上发布的解决方案，并给出了两个示例测试用例，但我无法得到正确的答案。 对于测试用例 1：： N=3 和 K=2 5 4 7 DAG将会是: 注：我构建上述DAG时考虑到： 设pi和pj是两个不同的问题。然后，我们将从pi到pj绘制一条有向边，当且仅当pj可以在pi之后的同一
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
给出了一个有向无环图G=(V，E)，如果需要，可以假定它是拓扑有序的。G中的边有两种类型的成本--名义成本w(e)和尖峰成本p(e)。 目标是找到从节点s到节点t的最短路径，使以下代价最小:sum_e(w(e))+max_e(p(e))，其中和和最大值在路径的所有边上取值。 标准动态规划方法表明，该问题在O(e^2)时间内是可解的。有没有更高效的办法解决？理想情况下，一个O(E*polylog(E
-
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。