6
$\begingroup$

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight is minimal.

I understand why the output consists of two $s$-$t$ paths, and the relationship between this and augmenting path flow algorithms on an intuitive level, however I fail to understand why the two paths the algorithm chooses necessarily minimize the weight.

I would appreciate if somebody could explain why the algorithm is correct. I don't have access to Suurballe's original paper and I can't follow the paper by Suurballe and Tarjan.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Don't have access? But there's a link to a PDF in the Wikipedia article you mentioned: A quick method for finding shortest pairs of disjoint paths $\endgroup$ – Pål GD Feb 8 '15 at 13:23
  • $\begingroup$ ... which is the Suurballe & Tarjan paper, and not the original paper by Suurballe. Argh. $\endgroup$ – Me. Feb 8 '15 at 13:43
  • $\begingroup$ I have the feeling the the core argument is hidden in the description of step 5 as stated on Wikipedia. $\endgroup$ – Raphael♦ Feb 8 '15 at 14:18
  • 2
    $\begingroup$ The way I see it it just justifies that the output is a pair of edge disjoint s-t paths, which is clear because essentially what we do is augmenting two paths in a flow network with capacities of 1 (i.e. the only edges which are reversed in the residual network are those which are in the shortest path, as this is the only case where the recalibrated weight can be 0). This also explains why the algorithm makes sense on an intuitive level because if all we wanted to do was finding a pair of edge disjoint paths, we could model it as a flow problem. $\endgroup$ – Me. Feb 8 '15 at 16:25
  • $\begingroup$ Above post ctd: However, this still doesn't explain why the algorithm works correctly, as it more or less is a handwaving argument. $\endgroup$ – Me. Feb 8 '15 at 16:26

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.