My guess: There's a small inaccuracy in the map data (I can think of a number possible ways this could happen) leading the cars to think that the dead end road

My guess: There's a small inaccuracy in the map data (I can think of a number possible ways this could happen) leading the cars to think that the dead end road connects somehow to where they want to go, but it doesn't. So they give up but don't update the data for the rest of the fleet. Something like that. Theres a false link in the graph.