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? :)
