Narendra is traveling from point A to point B and there are n toll posts along the way. Before starting the journey, Narendra is given, for each post 1 ≤ i < j ≤ n, the fee
to travel from post i to post j. The goal is to minimize the travel cost. The most efficient algorithm to solve this problem has the time complexity as
(A)$\theta(n)$
(B)$\theta (nlogn)$
(C)$\theta(n^2)$
(D)$\theta(n^3)$
So, there are n toll posts and we have to reach to point B from point A.
I thought of this like since there are n toll posts and after last toll post we will reach B.
So, we can consider it as a graph with n nodes and $\frac{n(n-1)}{2}$ edges.
So, in this graph, I want to find how from source i(Which will be the first toll post), I can reach the last toll post with minimum cost.
This can be done by running the Dijkstra single source shortest path algorithm on this graph
This graph has $|V|=n,|E|=O(n^2)$
Running time of Dijkstra using
(a)Binary heaps: $(V+E)logV$, and hence, in this case, it comes to be $\theta(n^2logn)$
(b)Fibonacci heaps: $E+VlogV=\theta(n^2)$, in this case.
The answer is given to be (C).
Is it like this has been solved using Dijkstra using fibonacci heaps?
Am I thinking in correct direction?
