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

will become

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.

| cite | improve this question | | | | |
  • 2
    $\begingroup$ Maybe I misunderstood the question, but why would all-pair shortest path care about parallel edges? Can't you just remove the redundant ones? $\endgroup$ – Christopher Boo Nov 27 '19 at 15:33
  • 1
    $\begingroup$ I hardly understand what is your question. You first talk about "all-pair" shortest path for which basically you should have a look to Floyd-Warshall algorithm. Then you talk about a specific expansion of your graph. But what is your actual issue ? $\endgroup$ – Optidad Nov 27 '19 at 16:09
  • $\begingroup$ I am sorry if my question was unclear. I know I can apply FW-algorithm to get all-pairs shortest paths. But that modification of the graph is necessary for the specific problem I am solving. However, I can not apply that expansion in an efficient way. I can not delete the parallel edges, since they are not redundant. Hence, my question. $\endgroup$ – Shiro-Raven Dec 4 '19 at 7:12

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.