I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges.
If N parallel edges exist between any two vertices A and B, I need to create N replicas of both vertices. Each replica of A will be connected to one and only one replica of B, and vice versa. In addition, all replicas of a vertex must be fully connected to each other.
As an example:-
A === B
A1 ----- B1 | | A2 ----- B2
Does this formulation match any well-defined graph theory problem? I am trying to come up with an algorithm that can make use of a GPU's speed, since the graphs I am dealing with can become huge, and I am trying to do it by manipulating the adjacency matrix.