<p>Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t_i$, the maximum flow from $S$ to $t_i$ is denoted by $f(S,t_i)$.</p>

<ol>
<li>Find $\max{f(S,t_i)}$ </li>
<li>Find $\max{d(S,t_i) * f(S,t_i)}$, where $d(S,t_i)$ represents the length of shortest path from $S$ to $t_i$</li>
</ol>

<p>I have found some papers about computing max flows of multiple targets on a planar graph, but is there any algorithm faster than computing $f(S,t_i)$ for $|T|$ times? </p>

CC BY-SA 3.0
2015-10-24T00:40:19.740Z
For number (2), why can't you compute (1), compute the shortest path from $S$ to each $t_i$ (which can be done using a single breadth-first search), and multiply?
Peter Shor 
CC BY-SA 3.0
2015-10-24T10:18:48.387Z
@PeterShor  Good. However BFS won't work because I failed to mention that weight might be assigned to edge, but dijkstra's algorithm is still much faster than computing $f(S,t_i)$ for $|T|$ times (I don't expect the algorithm of (1) could be faster than O((E+V)logV)). Anyway, thanks for your help, and the bottleneck is (1) now.
Zheng  Luo
<graph-theory><graph-algorithms><max-flow>
What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}
Zheng  Luo
# What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

(Asked by: username_0 on 2015-10-23)

Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t\_i$, the maximum flow from $S$ to $t\_i$ is denoted by $f(S,t\_i)$.

1. Find $\max{f(S,t\_i)}$
2. Find $\max{d(S,t\_i) \* f(S,t\_i)}$, where $d(S,t\_i)$ represents the length of shortest path from $S$ to $t\_i$

I have found some papers about computing max flows of multiple targets on a planar graph, but is there any algorithm faster than computing $f(S,t\_i)$ for $|T|$ times?

**Tags:** graph-theory, graph-algorithms, max-flow
> **Comments:**
> **username_1**: For number (2), why can't you compute (1), compute the shortest path from $S$ to each $t_i$ (which can be done using a single breadth-first search), and multiply?  
> **username_0**: @PeterShor  Good. However BFS won't work because I failed to mention that weight might be assigned to edge, but dijkstra's algorithm is still much faster than computing $f(S,t_i)$ for $|T|$ times (I don't expect the algorithm of (1) could be faster than O((E+V)logV)). Anyway, thanks for your help, and the bottleneck is (1) now.  

---

## 0 answers

