0
$\begingroup$

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.

$\endgroup$

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.