Restaurant supply route

[Avarentis]

I have a restaurants and my Job is to go and buy suples from different warehouses.
I have a list of needed supplies and their costs in each warehouse. Also I have a cost of traveling to destination and back.
My job is to buy supplies with lowest cost.
I can go to each warehouse buy there unlimited amount of supplies and I have to go back to central. Only then I can go to next warehouse, where I can buy different wares.

Example:
I have 5 warehouse(I-V) and I need 3 types of commodities.
The cost of travelling between each warehouse is on the picture, near each path. Costs of each commodity is in () near each warehouse.

[tiliavirga]

My job is to buy supplies with lowest cost.

It can be formulated as a minimum cost network flow problem.

The network consists of several stages. Each stage represents the purchase of one specific commodity. At each stage all warehouses are present and each is represented with a node. Each warehouse node at one commodity stage is linked with every node of the next stage. The central is represented with a source node and a sink node linked to all nodes of the first and last stage respectively. In the example there are 1 + 3*5 + 1 nodes. The number of links are 5 + 5*5 + 5*5 + 5.

The cost of every link can be calculated from the problem formulation and the solution is to find a minimum cost flow from source to sink. Due to the special structure of the network this problem can also be viewed as a shortest path in a DAG problem. According to Cormen (3'rd ed. p. 655) the problem can then be solved in linear time with complexity O(nodes + links) which means its quadratic in the number of warehouses.