2
$\begingroup$

Given an undirected graph and a start and end node, I am trying to find two node-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 node (other than the start or end node) can be visited 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 nodes in the first path may have blocked a possible and way shorter path.

I have tried implementing the node_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.

Improve this question
$\endgroup$
6
  • $\begingroup$ I don't understand what you want the output to be. Can you state the problem more precisely? I see that you have some constraints on the paths, but in what sense do you want them to be shortest? Do you want one to be the shortest path overall, and the second to be the shortest of all candidate paths that satisfy the constraints (i.e., are consistent with the first)? Do you want to minimize the sum of lengths of the two paths? Something else? I can't tell. $\endgroup$
    – D.W. ♦
    Mar 18, 2021 at 22:48
  • $\begingroup$ Possibly relevant: en.wikipedia.org/wiki/K_shortest_path_routing $\endgroup$
    – D.W. ♦
    Mar 18, 2021 at 22:48
  • $\begingroup$ Overall yes, I would like the two paths that overall give me the lowest cost. I mean, by using Dijkstra's I could potentially end up with a path with a very low cost from start to end. But by doing so, I might cut off an unfortunate node or edge, that might disconnects the entire graph for some large area. This means, that the second path might be very long. So if only the first path wouldn't have been the shortest, but maybe just a big longer, and then the second path could have been calculated as being also only a little bit longer (or something like that). Resulting in overall total cost. $\endgroup$
    – Denver Dang
    Mar 18, 2021 at 22:53
  • $\begingroup$ Can you edit the question to state the problem clearly? Please don't leave clarifications in the comments -- instead, edit the question so it reads well and is clear for someone who encounters it for the first time. I find the word "overall" unclear; if you want to minimize the sum of the lengths of the two paths, I would suggest saying that. $\endgroup$
    – D.W. ♦
    Mar 18, 2021 at 22:55
  • $\begingroup$ I have tried to edit my OP now. $\endgroup$
    – Denver Dang
    Mar 18, 2021 at 22:59

1 Answer 1

Reset to default
2
$\begingroup$

This can be solved by a small modification to Suurballe's algorithm, with $O(|E| + |V| \log |V|)$ running time. You might also be interested in Computing the k shortest edge-disjoint paths on a weighted graph.

Suurballe's algorithm works with directed graphs. You can convert an undirected graph to a directed graph by replacing each undirected edge $(u,v)$ with two directed edges $u \to v$, $v \to u$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Correct me if I'm mistaken, but Suurballe's algorithm is for directed graphs, right ? I am using a undirected graph. $\endgroup$
    – Denver Dang
    Mar 19, 2021 at 11:38
  • $\begingroup$ But yeah, I could just convert my undirected to a directed graph. Hmmm, this seems interesting. I am however a bit baffled that this isn't implemented in some of the network packages I've looked at. Or maybe they just don't call it Suurballe ? $\endgroup$
    – Denver Dang
    Mar 19, 2021 at 12:07
  • $\begingroup$ @DenverDang, see edited answer. $\endgroup$
    – D.W. ♦
    Mar 19, 2021 at 18:36

Your Answer

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

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