I have a directed graph that has a source node and a sink node and a subset of marked edges.
I need to find a path from source to sink that contains at least one marked edge and is cycle-free.
2
-
$\begingroup$ What have you tried? What approaches have you already considered? What's the fastest algorithm you've come up with so far? $\endgroup$– D.W. ♦Commented Dec 29, 2015 at 18:30
-
$\begingroup$ I have only implemented a solution that's not cycle-free. I ended up finding a better solution for my original problem that doesn't involve this question. @D.W. $\endgroup$– ToastCommented Dec 29, 2015 at 22:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If the path did not have to be cycle free this would be easy: let $s$ and $t$ be the source/sink, take two copies of the graph, say $(V_1, E_1)$ and $(V_2, E_2)$, and for any marked edge $\{v_i, v_j\}$ in the original graph, add $\{v_{1i}, v_{2j}\}$ and $\{v_{2i}, v_{1j} \}$ to the new graphs (connecting them), then find a path from $s_1$ to $t_2$.
For the cycle-less case, the best I can think of is a solution using max flow: iterate over all marked edges $\{u, v\}$, add a supersource and supersink to the graph, add edges from the supersource to the original source and sink $s$ and $t$, and edges from $u$ and $v$ to the supersink. Then find two vertex disjoint paths from the supersource to the supersink (we consider two paths to be vertex disjoint if the only shared vertices are the supersource and supersink, there are at most two of these paths). If no two paths exist, you cannot use the edge $\{u, v\}$, otherwise you can reconstruct the full path using the flow you found.
Finding these vertex disjoint paths is not entirely trivial, you'll need to transform the graph a little (see e.g. here), but it will only increase the size of the graph linearly.
