Given N cities and M planned infrastructure projects, I need to find an approach to determine the earliest date at which two specific cities will be connected.
Some cities resides on the same island and can therefore be easily reached from each other. These cities form a community. There are C such communities.
Example input:
Communities consisting of cities:
Planned infrastructure projects:
For example given the cities Chesney and Georgette, the earliest date in which these cities are connected is 2021-07-01.
I am thinking of two approaches that this problem can be modelled. Either as a graph problem, so it can be solved using an MST algorithm or by reducing it to a network flow. I see some remsebles to the Airline Scheduling problem, which can be solved using a network flow, which makes me think that this problem is more likely a network flow problem. However I am not quite sure how to model this specific problem as a network flow problem. Could someone guide me in the right direction?
You can solve this with Kruskal's algorithm, sorting the edges by completion date instead of weight.