How to use the transport network optimally?

Question

Algorithms

Given a transport network with a beginning and an end. From the beginning, cars drive out along the ribs. Machine speed - 1 edge per turn. Only 1 car can pass through one edge per turn. At each vertex, except for the beginning and end, there can only be 1 car. You need to find a path (a set of paths) that will take n cars in the minimum time.
Now the algorithm is as follows: we are looking for the minimum path, we consider the time for it. Next, we remove its vertices and in the cycle we look for the next minimum paths, we calculate the total time for the sum of each new and previous ones. The loop stops if adding a new path does not decrease the time.
The algorithm is stupid and skips optimal solutions. Please share your ideas about the implementation of the algorithm

Answer 1

I can't say how time-optimal this solution will be without knowing the expected size of the graph. But there is a solution through the maximum flow, which will definitely start the cars in the best way.
Inflate the graph by making copies of every vertex for every possible time. That is, if it is assumed that there is a solution no longer than 1000 time units, then create a graph with 1000 * V vertices, one for each vertex of the initial graph and possible time. For each edge of the input graph u->v, create an edge {u,t}->{u,t+1}. This graph has many input vertices (any time, start vertex) and many end vertices (any time). But there is no longer a condition for non-intersection of cars at the same time. Instead, car paths simply cannot cross vertices at all. After all, each vertex symbolizes the vertex + time.
Now let's transform the graph again - make a new input vertex and connect it to all the input vertices in this graph. Also make a new end vertex and connect it to all end vertices. Divide each remaining vertex into 2 - input and output. Let all the edges leading to this vertex into the input, and also bring all the edges from the initial vertex out of the output. Connect the input and output with an edge.
In this graph, the paths should no longer intersect along the edges (after all, each vertex is replaced by an edge between two new vertices) and all paths lead from the beginning to the end. To allow machines to intersect at the start and end vertex, do not split the start and end vertices of the graph and make the capacity of the edges from the start and end vertices equal to n. All other bandwidths are 1.
Now let the maximum flow in this scar, and it will find you some paths of cars that do not intersect along the edges. These paths uniquely give you the paths of the cars in the original graph - when to release the car and which path it goes.
To find the optimal path, run a binary search on the answer. So you chose the number 1000, created an artificial graph with time up to 1000 for all vertices. Launched in it the maximum flow. If he found less than n paths, then in 1000 units of time all n cars will not be allowed, try more time. If you have found at least n paths, then you can take any n of them.
The initial upper bound on time can be taken as n+V (V is a path in the graph, and all cars follow it in a column one after another).
Perhaps there is an improvement to this solution like this: Instead of binary search on the answer, you increase the maximum time by 1, add new vertices and edges to the graph and each time look for complementary paths (without clearing the maximum flow already found). This solution seems to be faster, but here you need to carefully understand what the residual network is.