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$
1
  • $\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
    Commented Jan 22, 2016 at 9:28

2 Answers 2

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$
3
  • 1
    $\begingroup$ What is the connection to the traveling salesman problem? I don't see it. $\endgroup$
    – bof
    Commented Jan 21, 2016 at 12:25
  • $\begingroup$ I also don't see a connection. $\endgroup$
    – ToiKri
    Commented Jan 21, 2016 at 14:05
  • $\begingroup$ Edited answer... $\endgroup$
    – Ove Ahlman
    Commented Jan 21, 2016 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .