具有两类代价的有向无环图中的最短路径
给出了一个有向无环图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，V))算法会很好。
其次，定义由状态(x，i)组成的状态空间，其中x是图中的一个节点，i位于1，2，…，E中。它表示“我们在节点x中，到目前为止我们看到的最高边权值p(e)是第i大”。
设V（x,i）是从s到x的最短路径（在经典意义上）的长度，其中所遇到的最大的p（e）是第i大的。对于x的任一前体y和1，…，E中的任一j,给定V(y，j)，很容易计算V(x，i)（有两种情况需要考虑-边y->x具有j次最大的权重，或者它没有）。
在每一个状态(x，i)，这个计算找到大约deg(x)值的最小值。因此，复杂度为O(E*sum_(x\inv)deg(x))=O(E^2)，因为每个节点都与E个不同的状态相关联。
共有1个答案
这只是一个2-近似，不是近似方案，但也许它启发某人想出一个更好的答案。
利用二分搜索，求出最小的尖峰代价θ*，使得C(θ)是使用尖峰代价≤θ的边的s-t路径的最小名义代价，我们有C(θ*)=θ*。每个解的名义成本或峰值成本至少与θ*一样大，因此θ*导致一个2-近似解。
二进制搜索中的每个测试都涉及在峰值代价≤θ的子集上运行Dijkstra，因此该算法需要时间O（E log2E)，如果您想要技术上使用Fibonacci堆，则需要时间O（(E+V log V）log E）。
-
给出了一个边上具有任意权的有向无环图和两个特定结点s和t，其中s的内度和t的外度为0。如何确定成本为正的s到t的最短路径？
-
在正加权有向无环图中，我有一个求最短路径的问题，但有最大N步（路径中的边）的限制。假定路径存在。图的另一个性质是，如果边（i,j）在图中，那么对于i 例如，考虑下图。 问题是最多使用k=3步（边）来寻找最短路径。答案是6（路径1->4->5->6)。
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。