1.3

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
  a ----------- c ----------- b
   \                         /
    \--------- d ---------- /

If the distance from a to b going through d is less than the distance from a to b going through c but there is a busy traffic intersection at d with a stop sign that is always backed up, then the route from a to b through c is faster, but the route through d is shorter.


For example,

[math]\displaystyle{ dist(a, c) = 10 }[/math] miles

[math]\displaystyle{ dist(c, b) = 5 }[/math] miles

So the distance from a to b through c is 15 miles. Assuming you drive 30 miles per hour, the time to travel this would be 30 minutes


[math]\displaystyle{ dist(a, d) = 5 }[/math] miles

[math]\displaystyle{ dist(c, b) = 5 }[/math] miles

So the distance from a to b through d is 10 miles. Assuming you drive 30 miles per hour, the time to travel this would be 20 minutes, but due to the busy intersection at d, you are delayed 15 minutes, the total time would be 35 minutes.

---

Another possible solution: You have a longer route with a higher speed and a shorter route with a lower speed. By choosing the numbers appropriately, you can make the longer route be the winner. The speed may be due to law, or due to traffic jam, or because of pot holes on the road :-)

Suppose road of length l1 has speed limit s1 and another road of length l2 has speed limit l2. The shorter route is determined by comparing l1 with l2. The faster route is determined by comparing l1/s1 with l2/s2. With positive numbers, if l1 > l2 but l1 < l2 * s1 / s2, then the faster route differs from the shorter route.


Back to Chapter 1