1
$\begingroup$

Say I have a graph G with n nodes and m edges. Give each edge a capacity. If I am working in discrete time intervals (say days), how do I find the fastest way to move x amount of product from a source node to an sink node when traveling across one edge takes 1 time interval ( 1 day). Note I can move product on different edges simultaneously. I have been combing network flow and transportation theory to find a solution, but can't seem to find a method that will allow me to compute the quickest path (without searching all possible paths).

$\endgroup$
  • $\begingroup$ Can you clarify what you mean by fastest way? You mention network flows which indicates that you are looking for a quickest flow. However, further below you say quickest path. Are you interested in a flow (using possibly several paths) or a single path? $\endgroup$ – philipph Jan 22 '16 at 9:28
1
$\begingroup$

After reading the question more carefully I've edited the answer. The following is heavily depending on the fact that it takes only 1 time interval, and that we may move product simultaneously:

  1. Remove all edges with capacity 0.
  2. By doing a breadth first search you may find the closest path, call it $p_1$ from one node in a graph to another, in this case your start node and your end node. This is the optimal path to push all your product on if it is possible (thus end algorithm here if this is done).
  3. If not all product is possible to be moved this way assume $k$ units are possible to move on $p_1$. Now create a new graph $G'$, by making a copy of $G$, but each let each edge in $p_1$ with capacity $t$ in $G$ get new capac $t-k$. Now repeat from step 1.

The breadth first search is very efficient , and thus the biggest problem is that we have to repeat it. However as you remove an edge each time the problem becomes smaller.

Old answer: This seems to be closely related to the travelling salesman problem. A problem which is so called NP-complete i.e. there is currently no known "good" algorithm to solve it, all solutions so far are about as good as searching all possible paths. If anyone would find a "good" solution it would solve the P vs NP problem which is a big unanswered question in mathematics.

$\endgroup$
  • 1
    $\begingroup$ What is the connection to the traveling salesman problem? I don't see it. $\endgroup$ – bof Jan 21 '16 at 12:25
  • $\begingroup$ I also don't see a connection. $\endgroup$ – ToiKri Jan 21 '16 at 14:05
  • $\begingroup$ Edited answer... $\endgroup$ – Ove Ahlman Jan 21 '16 at 14:37
0
$\begingroup$

You need to send a flow of value $x$ from the source to the sink with capacity constraints, and unit costs on every edge: I see it as a minimum cost flow problem.

There are many algorithms for this. See for example here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.