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.