I love these sorts of applied maths sorts of post! Nice work, interesting reading.

With the small graph in the post, finding the solution by searching backwards from "finished" graphs (ie. single-city) using dynamic programming should be simpler than beam search and guaranteed optimal.