TADM2E 1.3

From Algorithm Wiki
Revision as of 15:37, 11 September 2015 by Zapstar (talk | contribs) (Corrected the graph figure.)
Jump to: navigation, 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,

$ dist(a, c) = 10 $ miles

$ dist(c, b) = 5 $ 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


$ dist(a, d) = 5 $ miles

$ dist(c, b) = 5 $ 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.


Back to Introduction ...