# Self doubt

Question

To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going uphill and then get a nice breeze at the end of your run as you run faster downhill. Your run will start at home and end at work and you have a map detailing the roads with l road segments(any existing road between two intersections) and m intersections. Each road segment has a positive length, and each intersection has a distinct elevation. Assuming that every road segment is either uphill or downhill, give an efficient algorithm  to find out shortest route that meets above specification??

Answer 1

Since we are asked to find shortest path, we can use Dijkstra algorithm. We can see how to do it here.

'l' roads and 'm' segments can be viewed as a graph with 'l' edges and 'm' nodes. Now, there is an additional constraint here that we cannot simply consider all paths but any path must have continuous uphill paths followed by continuous downhill paths. In order to do this we can run Dijkstra algorithm twice, 

1. from the home as source and only considering uphill paths (from any node) till end, we update the shortest distance to each node, let it be $U_{i}.$
2. with the work as source and only considering downhill paths (towards any node) till home and again update the shortest distance to each node, let it be $D_i.$

Now, all we need to do is to visit each node and do $U_i + D_i$ and finally take the minimum value of it. The node corresponding to it will be the point where uphill path changes to downhill one. 

Complexity = Shortest path complexity + $O(m)$

$= O(l  + m \log m) + O(m)$

$ = O(l + m \log m).$ 

Comments

Dijkstra is implemented using priority queue, which mainly uses heap.

• Inserting all vertices in queue will done $O\left ( n log n \right )$ time by repeated insertion by bottom up heap construction method
• Overall while loop will run $\sum_{v\epsilon G}^{.}\left ( 1+deg\left ( v \right ) \right )logn$
• which is $O\left ( n+m \right )logn$
• Now for non negative weight dijkstra will work $O\left ( mlogn \right )$ time

right?

---

Heap construction is $O(n)$ rt?

Now, for Binary heap this is true, but Dijkstra can be done using Fibonacci heap which gives better asymtotic time complexity.

---

but why we use fibonacci heap here?
"Fibonacci heaps in constant amortized time, improving on the logarithmic merge time of a binomial heap"
https://en.wikipedia.org/wiki/Fibonacci_heap