Finding the minimum weight circuit that passes through vertices u and v

user_13587073 0
Viewed 101

I have an undirected and connected (not complete) graph of vertices, where u and v can be any 2 distinct vertices. I want to construct the minimum weight circuit that starts from a vertex u, passes through v, then returns back to u without repeating any edges. Can this be done by doing the following?

  1. Finding the shortest path from u to v - call this p1

  2. Removing all constituent edges of p1 from the graph

  3. Finding the new shortest path from v to u - call this p2

  4. Returning all deleted edges to the graph, and concatenating p1 and p2 together - call this c1

Is c1 the minimum weight circuit that can be constructed, considering the constraint of passing through both u and v? If so, how can I prove it, if not, why not?

It seems to make sense to me, as all the paths contained within c1 are also shortest paths themselves, however I can't quite shake the feeling that I might be missing something.

EDIT: I have changed "fully connected graph" to "connected graph". "fully" implied that the graph is complete, which is not what I meant.

graph-theory graph-algorithm algorithm
2 Answers

Here is a counterexample:

In a case of complete graph, assume all edges not shown in the picture to have some large weight (like 1000).

The p1 would find the shortest path 1 - 1 - 1 and exclude it, prohibiting the actual answer of 3 - 1 + 1 - 3.

As suggested by Falk Hüffner, this task can be solved by Edge disjoint shortest pair algorithm.

user_13493660

If I understand correctly, this is equivalent to finding two edge-disjoint paths from u to v while minimizing their total weight. This is a special case of Minimum Cost Flow with a flow of two, so it can be solved in polynomial time and is likely not NP-hard. Suurballe's algorithm solves it for directed graphs, and it should be possible to adapt it to undirected graphs (it seems that this Wikipedia page is attempting to do this).

user_3783600
Related