We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can be activated at any node u, such that time between u to v becomes (u,v)/3. The turbocharger has to be used just once. Find the minimum distance path between s to t.

My approach - Use BFS to calculate all the paths. When we find all the paths from s to t, apply brute force to each edge (u,v) and check the minimum result. This approach takes O(V+E) + O(E) time roughly. (I assume).

I am looking for suggestions and better approach to this problem. Please appreciate my learning phase and help me to do better at algorithms.
Thank You.
  • $\begingroup$ Is it possible to do better than $O(|V|+|E|)$ time? Can you prove it? $\endgroup$ – D.W. Dec 7 '20 at 0:00
  • $\begingroup$ finding all the paths take O(V+E) time as we have to apply BFS with certain restrictions i.e not to mark a node visited until there is no other path. Then, assigning the conditions of turbo charger may take extra O(E) time. There is no other way to do this from my point of view. $\endgroup$ – anony_std Dec 7 '20 at 1:59
  • $\begingroup$ There can be exponentially many paths, even if $G$ is directed and acyclic: Consider a graph with $2n+2$ vertices arranged in 2 rows of $n$ vertices each, with each vertex linked to the next vertex on its right in the same row, and also to the next vertex on its right in the other row. $s$ is linked to the two leftmost vertices, and the two rightmost vertices link to $t$. There are $2^n$ $s-t$ paths, because any subset of the $n$ vertices in the top row can be visited. $\endgroup$ – j_random_hacker Dec 7 '20 at 19:15

First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are generating all paths, each path visits at most all the nodes once, so the time complexity of your algorithm would actually be O(PN) where P is the total number of paths. In fact, it is likely way larger because each edge can be visited more than once.

However, there is another algorithm that can be applied to this non-negative edge-weight graph: Dijkstra's Algorithm.

To deal with the turbo charger, simply expand the graph such that each each state in your heap stores both the current weight and wether the charger has been used.

  • $\begingroup$ That's the suggestion I wanted. Thank you so much. @timg $\endgroup$ – anony_std Dec 11 '20 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.