Find a monotonic shortest path in a graph in O(E logV)

Question

Problem 34 of creative problems from this page.

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.

My question:

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?

Answer 1

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.

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. Preprocess the graph by sorting outgoing edges from each node (by weight).
2. Each node should contain position in the list of outgoing edges (initialized by position of the lightest edge).
3. There is no need for priority queue to support "decrease" operation (so it could be implemented by simple min-heap). Each vertex is inserted into priority queue and then never altered until it appears at the top of queue (as a result each vertex may be represented in the queue several times). Queue entry consists of a key (which is path length, as usual), vertex, and weight of incoming edge. So we may assume priority queue to contain incoming edges instead of vertices.
4. Relaxation procedure: pop edge (and hence vertex where this edge ends) from the queue; for all outgoing edges of the vertex in increasing order, starting from the position stored in graph node, and ending when outgoing edge's weight is greater or equal to the incoming edge's weight, push outgoing edge to priority queue and advance stored position.

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 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;
    }
}

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: