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

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:

I use modified Dijkstra algorithm to solve it : For example, if we want to find a best path in ascending order between source and every other vertex, use a Priority Queue PQ:

1. PQ.add(source, 0)
2. for other vertex, PQ.add(vertex, infinity)
3. while PQ is not empty, let vertex i = PQ.removeSmallest(); relax all ascending edges from i;

relax edges from i to p with weight:

if (disTo[p] > disTo[i] + weight && weight > weight[i, edgeTo[i]) {
   disTo[p] =  disTo[i] + weight;
   edgeTo[p] = i;
   PQ.changePriority(p, disTo[p]);
}