Help regarding a flow problem

Hi.
I Have a variant of the standard flow problem. … 1st let me state in simple terms the original flow problem ( if there is some mistake do let me know )
Say u have a graph with n nodes m edges … a source and a sink … u are given max no of items that can flow thorugh the edges … u want to send max number of items from source to sink
Notice that here the length of the edges doesn’t matter … I was thinking of a condition where each of the edges besides a max capacity also has a length … and suppose source has infinite supply of items … and that speed of all items is uniform …so now , unlike the original flow problem. …certain items may reach a particular vertex earlier than some items coming from other edges. … and that at no item can be stored in any vertex … so there is a constant flow… much like real life water flow … what algo should u use to solve the problem. .

Basically, say in the standard flow problem. … u don’t have any edge weight parameter … but if there were any… then some items may reach a particular vertex earlier than some other items (speed constant. . Do time proportional to speed) … and then the traditional prob would be restated as u ARE ALLOWED TO TEMPORARILY store few items at a vertex … and when all the items that can reach the vertex have reached … u do further calculations … but in my case… u ARE NOT ALLOWED TO TEMPORARILY STORE items … so everything has to be in constant flow.
Please reply if anyone has some solution…
Thanks in advance!!!

1 Like

There is something called “Minimum Cost Flow”, I think that is what you’re looking for (correct me if I’m wrong), I myself have not learned any algorithms for that, but I can give you links to a few resources :


I think in your case, the ‘cost’ of each edge will simply be its length.