Q:

Graph Puzzle with labels

There is a Graph G(V,E).  All nodes and edges are numbered.  Two edges can have same number but all nodes have a unique number.  
A path 
$ v_1, v_2,v_3,...,v_k $ exists if and only if the edge connecting the nodes in the path is in increasing order.  I am interested in finding the maximum valued reachable node for each node in the graph. 
I have thought of doing Depth First Traversal starting from the highest valued node and marking all those that can visit this node, and so on.  But using this approach, we must visit a node more than once. 

A:

I think you can do it in $|E|\log |E|$. 
Sketch:
For simplicity, let's first assume that the labels of the edges are unique.  In such case, start with an array $M : V \to V$ initialized with the labels of $V$. Then sort all the edges descending by their labels and for each edge $(u,v)$ set $$M[v] = M[u] = \max\{M[v],M[u]\}.$$
The invariant is that $M[v]$ contains the highest node-label reachable from $v$ via edges with labels at least $\mathtt{label}[(u,v)]$.
When the edge-labels aren't unique, the matter complicates a bit, because there might be a chain of edges having the same label.  If the edge-labels on paths should be non-decreasing (weakly increasing), then a careful resorting of current edge-label level by $\max\{M[v_1], M[v_2]\}$ seems like enough (e.g., visiting the changed nodes first is equivalent to a DFS using edges with the same edge-label).  For strictly increasing labels on paths use two passes: first gather updates, second apply them. 
I hope this helps $\ddot\smile$

