Question 1

Hint: relax edges in ascending order to find a best monotonically increasing path; relax edges in descending order to find a best monotonically decreasing path.



Question 2

Hint: compute the shortest path distances from s to every vertex and the shortest path distances from every vertex to t.



Question 3

Hint: compute the shortest path from s to every vertex; compute the shortest path from every vertex to t; combine.