1
$\begingroup$

Suppose an undirected (non-negative) weighted graph $G$. Given two of its nodes, we are asked to find the shortest simple cycle that contains at least those two. To clarify, the cycle can't repeat edges but can repeat nodes.

I recently found out Suurballe's algorithm which is said to compute such shortest cycle. Briefly, this algorithm runs Dijkstra twice: first to find the shortest path between the nodes and then to find the second shortest path that is edge-disjoint with the first path. In order to maintain this disjointness, it modifies a bit the inital graph, before the second run of Dijkstra (but that's not important here).

What results would that algorithm give for the graph below and nodes $A$ and $D$?

enter image description here

If I have understood correctly, with Suurballe's algorithm the first run of Dijkstra would give the path $A\to B\to C\to D$ and the second run would give $A\to D$. Then, the final cycle would be $A\to B\to C\to D\to A$ with total cost 18.

But this graph has a shorter cycle: $A\to C\to D\to B\to A$ with total cost 17. Note that this cycle can be obtained by combining paths $A\to B\to D$ and $A\to C\to D$, none of which is a shortest path between $A$ and $D$.

What have I gotten wrong?

$\endgroup$
1
$\begingroup$

After the first run of Dijkstra has found $A\to B\to C\to D$, the weights of the graph are changed for the second run. I have not checked it, but I guess that in that updated graph, the second run will find path $A\to C\to B\to D$.

These two paths traverse edge $BC$ in opposite directions, so that section is removed. The remaining parts of the paths are reassembled (head of one path with the tail of the other) to get the two paths $A\to C\to D$ and $A\to B\to D$. Together these form the shortest cycle $A\to C\to D\to B\to A$.

The example in the wiki page illustrates the process quite well.

$\endgroup$
  • $\begingroup$ I checked it and indeed that's what happens. Silly me... :) $\endgroup$ – frabala Mar 19 at 15:45

Your Answer

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

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