Here an interesting graph problem I've recently saw:

After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with city-to-city distances (in term of number of days), but it has a limited fuel range. Refueling requires a full day's stop. Fortunately, they possess a police schedule detailing when each city will be patrolled. Entering or refueling in these patrolled cities increases their capture risk. If k days are passed in a city where police is present, the risk of being captured is computed by $f(k)$ (tipically, $f$ is an increasing function that tends to 1 when $k$ approach infinity). However, they can opt to halt in non-patrolled cities to decrease detection chances.

Data provided:

  • Graph $G = (V, E)$ of some U.S. cities that connect Washington to Miami with distances in days between them.
  • Police patrol schedule specifying when each city will be visited (typically a dictionary of type $\{\text{city}: [\text{days of visit}]\}$.
  • Vehicle's fuel capacity $cap$ in terms of travel distance.
  • Countdown timer $count$ indicating when the boat in Miami will depart.

The goal is to create an algorithm that evaluate the probality of reaching Miami on time without getting captured, considering the given mathematical model for capture probability.

What do you think? :)

  • $\begingroup$ What have you tried and where did you get stuck? $\endgroup$
    – Juho
    Oct 21, 2023 at 16:09
  • 1
    $\begingroup$ Where did you encounter this graph problem? We require you to credit the original source: cs.stackexchange.com/help/referencing. Also, we're not looking for posts that contain the text of an exercise-style task and a request for us to solve it. We're trying to build up an archive of knowledge that will be useful to others in the future. Please edit your post based on the feedback you've received. $\endgroup$
    – D.W.
    Oct 22, 2023 at 1:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.