C  Upside Down Dijkstra

Since the wrong Dijkstra’s algorithm always takes the current maximum distance, that means whenever a new vertex is processed, if it is adjacent to at least one unprocessed vertex, the next processed vertex must be one of those adjacent to the current vertex. If all of its adjacent vertices are already processed, then this vertex will not generate new entries to the heap and the next maximum distance comes from the next unprocessed "child" of its closest "ancestor". If observed more closely, notice that the order of vertices processed looks like an arbitrary naive DFS that does not go through the same vertices more than once. Each vertex in the DFS only unrecurse back to its source parent when all of its neighboring vertices are already processed.

The solution is to check whether or not \(S\) follows a possible naive DFS order, using a stack. A vertex can only be pushed into the stack if it is adjacent to the current top. The top of the stack can only be popped when it has already had all of its neighbors processed. The edge weights can be calculated based on the order of vertices pushed into the stack interacting with the current state of the stack.

Each iteration might have a worst case of \(O(n)\) time complexity because of the need to iterate edges, so some non-trivial optimizations might be needed to make sure that the total time complexity is still within \(O(n+m)\).