how to find all edge-disjoint equi-cost paths in an undirected graph between a pair of nodes?

Question

Given an undirected graph G = (V, E), the edges in G have non-negative weights.

[1] how to find all the edge-disjoint and equal-cost paths between two nodes s and t ?

[2] how to find all the edge-disjoint paths between two nodes s and t ?

[3] how to find all the vertex-disjoint and equal-cost paths between two nodes s and t ?

[4] how to find all the vertex-disjoint paths between two nodes s and t ?

Any approximation algorithms instead ?

Answer 1

Build a tree where each node is a representation of a path through your unidirectional graph.

I know, a tree is a graph too, but in this answer I will use the following terms with this meanings:

• vertex: is a vertex in your unidirectional graph. It is NOT a node in my tree.
• edge: is an edge in your unidirectional graph. It is NOT part of my tree.
• node: a vertex in my tree, not in your graph.
• root: the sole node on top of my tree that has no parent.
• leaf: any node in my tree that has no children.

I will not talk about edges in my tree, so there is no word for tree-edges. Every edge in this answer is part of your graph.

---

Algorithm to build the tree

The root of the tree is the representation of a path that contains only of the vertex s and contains no edge. Let its weight be 0.

Do for every node in that tree:

Take the end-vertex of the path represented by that node (I call it the actual node) and find all edges that lead away from that end-vertex.
If: there are no edges that lead away from this vertex, you reached a dead end. This path never will lead to vertex t. So mark this node as a leaf and give it an infinite weight.
Else:

For each of those edges:
add a child-node to the actual node. Let it be a copy of the actual node. Attach the edge to the end of path and then attach the edges end-vertex to the path too. (so each path follows the pattern vertex-edge-vertex-edge-vertex-...)
Now traverse up in the tree, back to the root and check if any of the predecessors has an end-vertex that is identic with the just added end-vertex.
If you have a match, the newly generated node is the representation of a path that contains a loop. Mark this node as a leaf and give it an infinite weight.
Else If there is no loop, just add the newly added edges weight to the nodes weight. Now test, if the end-vertex of the newly generated node is the vertex t.
If it really is, mark this node as a leaf, since the path represented by this node is a valid path from s to t.

---

This algorithm always comes to an end in finite time. At the end you have 3 types of leafs in your tree:

• nodes that represent dead ends with an infinite weight
• nodes that represent loops, also with an infinite weight
• nodes that represent a valid path from s to t, with its weight beeing the sum of all edges weights that are part of this path.

Each path represented by a leaf has its individual sequence of edges (but might contain the same sequence of vertexes), so the leafs with finite weights represent the complete set of edge-disjoint pathes from s to t. This is the solution of exercise [2].

Now do for all leafs with finite weight:
Write its weight and its path into a list. Sort the list by the weights. Now paths with identic weight are neighbours in the list, and you can find and extract all groups of equal-cost paths in this sorted list. This is the solution of exercise [1].

Now, do for each entry in this list:
add to each path in this list the list of its vertexes. After you have done this, you have a table with this columns:

• weight
• path
• 1st vertex (is always s)
• 2nd vertex
• 3rd vertex
• ...

Sort this table lexigraphic by the vertexes and after all vertexes by the weight (sort by 1st vertex, 2nd vertex, 3rd vertex ,... ,weight) If one row in this sorted table has the same sequence of vertexes as the row before, then delete this row.

This is the list of all vertex-disjoint paths between two nodes s and t, and so it is the solution of exercise [4].

And in this list you find all equal-cost paths as neighbours, so you can easily extract all groups of vertex-disjoint and equal-cost paths between two nodes s and t from that list, so here you have the solution of exercise [3].