# What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

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?

• 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 Oct 24 '15 at 0:40
• @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 Oct 24 '15 at 10:18