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?

  • $\begingroup$ 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? $\endgroup$ – Peter Shor Oct 24 '15 at 0:40
  • $\begingroup$ @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. $\endgroup$ – Zheng Luo Oct 24 '15 at 10:18

Your Answer

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

Browse other questions tagged or ask your own question.