# Is Suurballe's algorithm optimal?

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$$?

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?

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$$.