在O(E logV)中查找图中的单调最短路径

Question

此页面中的创意问题34 .

单调最短路径.给定边加权有向图,找到从s到每个其他顶点的单调最短路径.如果路径上每个边缘的权重严格增加或严格减小,则路径是单调的.

部分解决方案:按升序放松边缘,找到最佳路径; 然后按降序放松边缘并找到最佳路径.

我的问题:

假设我们按降序放松边缘,并且我们可以在一个点上选择多于1个边缘.我们将在什么基础上选择下一个优势？理想情况下,我们应该选择较小的边缘,因为它会最小化到该顶点的距离.但是如果离开它的所有边都具有大于当前边的权重的权重,那么这样做可能导致没有来自该顶点的进一步路径.

那么,我们怎样才能解决这个问题呢？

Answer 1

这个问题可以通过修改后的 Dijkstra 算法来解决。主要的一点是放松不应该min在每个图节点（像往常一样）中进行操作，而是在优先级队列中进行。

以下是对常用 Dijkstra 算法的修改列表。我只考虑边缘的升序松弛，这会导致最短路径严格减少（要增加最短路径，请更改第 2 项和第 4 项）：

1. 通过对每个节点的输出边进行排序（按权重）来预处理图形。
2. 每个节点都应包含出边列表中的位置（由最亮边的位置初始化）。
3. 优先级队列不需要支持“递减”操作（因此可以通过简单的最小堆来实现）。每个顶点都被插入到优先级队列中，然后在它出现在队列顶部之前永远不会改变（因此每个顶点可能会在队列中多次表示）。队列条目由一个键（通常是路径长度）、顶点和传入边的权重组成。所以我们可以假设优先队列包含传入的边而不是顶点。
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 的帮助下生成），其中突出显示了严格递减的最短路径之一：