title: Find a monotonic shortest path in a graph in O(E logV)
body: <p>Problem 34 of creative problems from <a href="http://algs4.cs.princeton.edu/44sp/" rel="noreferrer">this page</a>.</p>
  <blockquote>
  <p><strong>Monotonic shortest path.</strong> 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.</p>
  <p><strong>Partial solution</strong>: relax edges in ascending order and find a best path; then relax edges in descending order and find a best path.</p>
  </blockquote>
  <p>My question:</p>
  <p>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.</p>
  <p>So, how can we solve this problem?</p>