I learnt about Suurballe's algorithm which I would like to implement for undirected graphs. All what I know are the following:

(1) provide a simple, weighted undirected, 2-edge connected graph $G=(V,E,w)$, where a $w$ positive weight function over the edges;

(2) select two nodes $s,t \in V$ (to determine two edge-disjoint paths of minimum length from $s$ to $t$, denoted with $P$ and $Q$);

(3) run Dijkstra's algorithm on $G$ from $s$ and save the shortest path $P'$ from $s$ to $t$;

(4) replace the w(u,v) edge weights with $w(u,v)+d(u)-d(v)$ for all $(u,v) \in E$, where $d(u)$ is the distance of $u$ from $s$;

(5) give directions to the edges (???);

(6) duplicate all the nodes of $P'$ in $G$ expect for the start and end points;

(7) put the edges of $P'$ into $G$ with reverse directions;

(8) find the $Q'$ shortest path from $s$ to $t$ in the modified $G$ graph;

(9) delete the duplicated nodes from $G$ (???);

(10) remove the common edges of $P'$ and $Q'$ and decompose them into two edge-disjoint paths, $P$ and $Q$ (???)

Could you please explain those points designated with three question marks (5, 9, 10)? I do not insist on using (1)-(10): if you have a simpler description, it is also acceptable for me.


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.