1
$\begingroup$

Given an undirected graph and a start and end node, I am trying to find two edge-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, end at the end node, and no edge can be traversed by both nodes. Is there an efficient algorithm to solve this problem?

I know that if I just need the shortest path, I can use Dijkstra's algorithm, but finding one path with Dijkstra's algorithm and then searching for another is sometimes not optimal at all, since edges in the first path may have blocked a possible and way shorter path.

I have tried implementing the edge_disjoint_path algorithm from the Python networkx package. But I must say that the result is very varying from okay to really bad. My network is not that big. "Only" 6000 nodes and 7500 edges.

$\endgroup$
5
  • $\begingroup$ Suurballe's algorithm solves this for directed graphs in $O(|E| + |V| \log |V|)$ time (see also en.wikipedia.org/wiki/Edge_disjoint_shortest_pair_algorithm), but it's not clear to me how to do this for undirected graphs -- I don't know if Suurballe's algorithm can handle this case as well. $\endgroup$
    – D.W.
    Commented Mar 19, 2021 at 18:36
  • $\begingroup$ Strange... This question is exactly as cs.stackexchange.com/questions/136807/… $\endgroup$
    – HEKTO
    Commented Mar 22, 2021 at 4:01
  • $\begingroup$ @HEKTO, that's for node-disjoint paths, this is for edge-disjoint paths. Initially both questions were asked in one post, but I separated them out into two posts. See cs.stackexchange.com/questions/136807/… and the revision history of that question. $\endgroup$
    – D.W.
    Commented Mar 22, 2021 at 8:27
  • $\begingroup$ Is there a reason why the node-disjoint version is answered, but not the edge-disjoint version? $\endgroup$ Commented Mar 12 at 14:57
  • $\begingroup$ @KennethKho, I don't know how to solve the edge-disjoint version, but if you do, I'd be interested to see your answer! $\endgroup$
    – D.W.
    Commented Mar 12 at 16:15

1 Answer 1

1
$\begingroup$

I think it is possible to use Suurballe's algorithm for this case by just replacing every undirected edge with two directed edges in each direction.

This is because Suurballe's algorithm would never choose two paths $P_1, P_2$, s. t. $e_x \in P_1$ and $\overleftarrow{e_x} \in P_2$ ($\overleftarrow{e_x}$ is the opposite edge of $e_x$). The proof is by contradiction:

Assume the two edge-disjoint paths with the shortest length would be $P_1 = e_{i_1}, \dots e_{i_{a-1}}, e_{i_{a}},e_{i_{a+1}} \dots e_{i_k}$ and $P_2 = e_{j_1}, \dots e_{j_{b-1}}, e_{j_{b}},e_{j_{b+1}}, \dots e_{h_l}$ with $e_{i_a} = \overleftarrow{e_{j_b}}$.

But then the two paths $e_{i_1}, \dots e_{i_{a-1}}, e_{j_{b+1}} \dots e_{j_l}$ and $e_{j_1}, \dots e_{j_{b-1}}, e_{i_{a+1}} \dots e_{i_k}$ would obviously be shorter and still edge-disjoint.

Because Suurballe's algorithm is never choosing opposite edges and is correct for the directed case, it works for undirected graphs as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.