2
$\begingroup$

Question: If you were on an island(Vertex) which are connected to multiple other islands, and to get from island A to B it takes time T and does damage D to your boat. What is the fastest route from A to B such that the total damage is strictly less than a given value H.

I tried using Dijkstra's algorithm to build a sub-tree however the shortest route may not be acceptable since the total damage could be greater than H. Any suggestions? Please keep the answer simple since I am a high school student.

$\endgroup$
1
$\begingroup$

We can create a new graph consisting of $N\cdot (H + 1)$ nodes and apply the Dijkstra algorithm on that graph. We will denote the new nodes as $(u, h):$ which means that the boat is at island $u$ and has been damaged by $h$ units, where $h$ is between $0$ and $H$. For each edge $(u, v, d, t)$ that goes from island $u$ to island $v$ while taking $d$ damage and $t$ time, we will create multiple edges in the new graph $((u, h), (v, h+d), t)$ (for $0 \leq h \leq H-d$). Your starting node will be $(A, 0)$ and to find the shortest path to $B$ you need to apply the Dijkstra algorithm and take the minimum time to $(B, h)$ for some $h$ between $0$ and $H$.

$\endgroup$
  • $\begingroup$ Why do we need new nodes? Cant we simply add a new parameter as you said to each node which will track the damage along with distance. Whenever during djkistra step we update distance we also update damage. When we find that damage is more than given damage we don't update the distance and damage as that particular path is not feasible. In the end whatever reaches the target node with minimum damage will give the answer. $\endgroup$ – noman pouigt Jan 3 '18 at 22:33
  • $\begingroup$ Minimum damage does not guarantee minimum time. For example the graph with the edges (A, B, 0, 1) and (A, B, 1, 0) (with H=1) is a counter example to your suggestion. $\endgroup$ – qvian Jan 4 '18 at 14:22

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.