在O（E logV）中查找图中的单调最短路径
此页面中存在创意问题的问题34。
单调最短路径。 给定一个边加权有向图，找出从s到其他每个顶点的单调最短路径。 如果路径上每个边的权重严格增加或严格递减，则路径是单调的。
部分解决方案 ：按升序放松边缘并找到最佳路径; 然后按降序放松边缘并找到最佳路径。
我的问题：
假设我们按照降序来放松边缘，并且我们可以选择多于一个边缘来选择一个点。 我们选择下一个优势的依据是什么？ 理想情况下，我们应该选择较小的边缘，因为它会最小化到该顶点的距离。 但是，如果所有离开它的边都具有大于当前边的权重的权重，那么这样做可能不会从该顶点产生更多路径。
那么，我们如何解决这个问题呢？
这个问题可以通过修改Dijkstra算法来解决。 主要的一点是，放松不应该在每个图节点（像往常一样）中进行min操作，而应该放在优先级队列中。
以下是通常Dijkstra算法的修改列表。 我只考虑边缘按升序放松，这会导致严格缩短最短路径（以获得最短路径，改变项目2和4）：
该算法保证每条边最多处理一次（如果我们考虑严格递减和严格递增路径，则处理两次），因此其复杂度为O（E log E）。
C ++ 11实现：
void getDecreasingSP(Vertices& vertices, Edges& edges, int src)
{
for (auto& v: vertices)
sort(begin(v.outEdges), end(v.outEdges),
[&](int from, int to)
{
return edges[from].weight < edges[to].weight;
});
PQ pq;
auto& src_v = vertices[src];
for (auto e: src_v.outEdges)
{
QEntry entry {edges[e].weight, e};
pq.push(entry);
++src_v.pos;
}
while(!pq.empty())
{
QEntry top = pq.top();
pq.pop();
auto& v = vertices[edges[top.inEdge].to];
while (v.pos < int(v.outEdges.size()) &&
edges[v.outEdges[v.pos]].weight < edges[top.inEdge].weight)
{
auto e = v.outEdges[v.pos];
edges[e].backPtr = top.inEdge;
QEntry entry {top.pathWeight + edges[e].weight, e};
pq.push(entry);
++v.pos;
}
if (v.backPtr == -1)
v.backPtr = top.inEdge;
}
}
另见Ideone的工作代码。 并且通过Graphviz帮助显示图形（由此代码生成），其中严格递减的最短路径之一被突出显示：
