From Labels to Graph: what machine learning approaches to use?

Imagine a world where we have places (e.g., cities, restaurants, national parks, etc.) but no roads connecting them.

Our objective is to build roads connecting any two places while going through some given places. For instance, connect Seattle to San Francisco and make sure the connection goes through restaurants X and Y and goes through the Red Wood national park. Note, there is not necessarily one possible road, hence multiple options as output are also acceptable.

We have some roads as examples to train the system. For instance, we have a road from Washington DC to Boston that goes through Baltimore.

So, the input to a machine learning system will be a list of strings (e.g., city names and places to go through) and the expected output is a tree/graph that connects the given points.

(Note, this cannot be a graph traversing problem, as a path the connects the points does not exist.)

I want a machine learning model that can produce/generate a novel graph in the output given a set of labels.

Any thoughts on what ML machine learning methods I can use and where to start?

---

Update 1

Note that I have neither of the following:

1. A graph of route(s) from Seatle to San Francisco;
2. A larger graph that contains a route from Seatle to San Francisco.

Instead, I have graphs for routes from Los Angles to Texas (with stops for eating and seeing landscape), from Milan to Rome, and etc.

Therefore, I think this is not a graph searching problem.

Update 2

I take that the initial question was not clear, so I reworded it.