在O(E logV)中的图形中找到单调最短路径 [英] Find a monotonic shortest path in a graph in O(E logV)

问题描述

来自此页面的问题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):

1. 通过对每个节点的输出边缘(按权重)进行排序来对图形进行预处理.
2. 每个节点都应在输出边缘列表中包含位置(通过最亮边缘的位置初始化).
3. 不需要优先级队列来支持减少"操作(因此可以通过简单的min-heap实现).每个顶点都插入到优先级队列中，然后再进行更改，直到它出现在队列的顶部为止(因此，每个顶点可能会在队列中多次出现).队列条目由一个键(通常是路径长度)，顶点和传入边缘的权重组成.因此，我们可以假设优先级队列包含输入边而不是顶点.
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)中的图形中找到单调最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！