I would like to implement the shortest pairs of edge-disjoint paths of Suurballe and Tarjan for multigraphs in the interpretation of Banerjee et al. (http://web.cs.iastate.edu/~pavan/papers/short.pdf, relying only on Section 3).

As regards simple graphs, this algorithm can be defined for a G=(V,E) simple graph having a source s and nonnegative edge costs c(u,v) as follows:

(1) Construct the shortest path tree T rooted at s for G using the Dijkstra algorithm.

(2) Reduce the cost on all edges (a,b) as c'(a,b)=c(a,b)+d(a)-d(b), where d(a) is the distance of vertex a from vertex s.

(3) Create an auxiliary graph G'=(V',E') in the following way:

(3.1) set V'=V and E' = empty,

(3.2) for each nontree edge (a,b) of E\T:

(3.2.1) define V * as the set of nodes in the path between a and b in T except for b,

(3.2.2) for each v' of V *: set E'=E' U {(v',b)} and c'(v',b)=c'(a,b).

(4) Construct a shortest path tree T' rooted at s for G' weighted by the c' function, using the Dijkstra algorithm.

(5) Save the predecessor of each vertex x in T' as q(x) and the tail of the nontree edge in G which caused the insertion of the (q(x),x) in G'.

(6) Create the pairs of edge-disjoint paths for each v of V in the following manner:

(6.1) Mark all the vertices in the shortest path from v to s in G.

(6.2) Generate the paths by two iterations of the step Traversal given below. In each iteration one path of the shortest pairs is generated.

Traversal: Define x=v, the path to be empty and repeat the following steps until x=s. If x is marked then unmark it and add (p(x),x) to the path, or else add (y,x) to the path, where y is the parent of x in T.

Could you please help me how to reformulate the algorithm for multigraphs? I guess that G', p(), q(), and Traversal of Section 3 in paper of Banerjee et al. should be modified somehow, but I don't know how.


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.