来自此页面的问题34.
单调最短路径.给定边加权的有向图,找到从s到其他顶点的单调最短路径.如果路径上每个边缘的权重都严格增加或严格减少,则该路径是单调的.
Monotonic shortest path. Given an edge-weighted digraph, find a monotonic shortest path from s to every other vertex. A path is monotonic if the weight of every edge on the path is either strictly increasing or strictly decreasing.
部分解决方案:以升序放宽边缘并找到最佳路径;然后以降序放宽边缘并找到最佳路径.
Partial solution: relax edges in ascending order and find a best path; then relax edges in descending order and find a best path.
我的问题:
假设我们以降序放宽边缘,并且在一个点上可以选择1个以上的边缘.我们将在什么基础上选择下一个优势?理想情况下,我们应该选择较小的边缘,因为它将使到该顶点的距离最小化.但是,如果离开该顶点的所有边缘的权重都大于当前边缘的权重,那么这样做可能导致该顶点不再有路径.
Suppose we are relaxing edges in descending order and we have an option of more than 1 edge to take at a point. On what basis will we choose the next edge to take? Ideally we should choose the smaller edge as it will minimize the distance to that vertex. But doing this may result in no further paths from that vertex if all edges leaving it have a weight that is greater than current edge's weight.
那么,我们如何解决这个问题?
So, how can we solve this problem?
推荐答案可以通过修改的Dijkstra算法解决此问题.要点是,放松不应在每个图节点(通常)中使用min操作完成,而应在优先级队列中进行.
This problem could be solved by modified Dijkstra’s algorithm. The main point is that relaxation should be done not with min operation in every graph node (as usual) but in the priority queue.
以下是Dijkstra常用算法的修改列表.我只考虑边缘的升序松弛,这会导致严格缩短最短路径(要增加最短路径,请更改项目2和4):
Here is the list of modifications for usual Dijkstra’s algorithm. I consider only edges' relaxation in ascending order, which results in strictly decreasing shortest path (to get increasing shortest path, alter items 2 and 4):
此算法保证每个边缘最多处理一次(如果同时考虑严格减少和严格增加的路径,则处理两次),因此其复杂度为O(E log E).
This algorithm guarantees that each edge is processed at most once (or twice if we consider both strictly decreasing and strictly increasing paths), so its complexity is O(E log E).
C ++ 11实现:
C++11 implementation:
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的帮助下生成)突出显示了严格减少的最短路径之一:
See also working code on Ideone. And visualization of the graph (produced by this code with help of Graphviz) where one of strictly decreasing shortest paths is highlighted:
更多推荐
在O(E logV)中的图形中找到单调最短路径
发布评论