2

Suppose I have a weighted non-directed graph G = (V,E). Each vertex has a list of elements.

We start in a vertex root and start looking for all occurances of elements with a value x. We wish to travel the least amount of distance (in terms of edge weight) to uncover all occurances of elements with value x.

The way I think of it, a MST will contain all vertices (and hence all vertices that satisfy our condition). Therefore the algorithm to uncover all occurances can just be done by finding the shortest path from root to all other vertices (this will be done on the MST of course).

Edit : As Louis pointed out, the MST will not work in all cases if the root is chosen arbitrarily. However, to make things clear, the root is part of the input and therefore there will be one and only one MST possible (given that the edges have distinct weights). This spanning tree will indeed have all minimum-cost paths to all other vertices in the graph starting from the root.

Improve this question
5
  • What exactly does “travel” mean? Are you looking for a single path? Commented Nov 17, 2011 at 2:27
  • The Steiner tree problem in graphs may be relevant. Commented Nov 17, 2011 at 2:38
  • @Per: I can't see the relevance of such complex tecnique. Could you elaborate? Commented Nov 17, 2011 at 3:20
  • @chac Minimum-cost subgraph that connects all of the nodes labeled x. Commented Nov 17, 2011 at 3:26
  • @Per: I see. You mean extra intermediate vertices and edges are all vertices not labelled x. Ok. Commented Nov 17, 2011 at 3:59

4 Answers 4

Reset to default
4

I don't think this will work. Consider the following example:

 x
 |
 3
 |
 y--3--root
 |     /
 5    3
 |   /
 |  /
  x

The minimum spanning tree contains all three edges with weight 3, but this is clearly not the optimum solution.

If I understand the problem correctly, you want to find the minimum-weight tree in the graph which includes all vertices labeled x. (That is, the correct answer would have total weight 8, and would be the two edges drawn vertically in this drawing.) But this does not include your arbitrarily selected root at all.

I am pretty confident that the following variation on Prim's algorithm would work. Not sure if it's optimal, though.

Let's say the label we are looking for is called L.

  1. Use an all-pairs shortest path algorithm to compute d(v, w) for all v, w.
  2. Pick some node labeled L; call this the root. (We can be sure that this will be in the result tree, since we are including all nodes labeled L.)
  3. Initialize a priority queue with the root initialized to 0. (The priority queue will consist of vertices labeled L, and their minimum distance from any node in the tree, including vertices not labeled L.)
  4. While the priority queue is nonempty, do the following:
    1. Pick out the top vertex in the queue; call it v, and its distance from the tree d.
    2. For each vertex w on the path from v to the tree, v inclusive, find the nearest L-labeled node x to w, and add x to the priority queue, or update its priority. Add w to the tree.
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I'm not sure I understand the question properly, but it seems to me that the root is not chosen arbitrary, but it's part of the input and it has be in the result.
I think that the MST it's the solution in your example
1

The answer is no, if I'm understanding correctly. Finding the minimum spanning tree will contain all vertices V, but you only want to find the vertices with value x. Thus, your MST result may have unneeded vertices adding extra path length and therefore be sub-optimal.

Improve this answer

Comments

0

An example has been given where the MST M1 from Root differs from an MST M2 containing all x nodes but not containing Root.

Here's an example where Root is in both MST's: Let graph G contain nodes R,S,T,U,V (R=Root), and a clockwise path R-S-T-U-V-R, with edge weights 1,1,3,2,2 going clockwise, and x at R, S, T, U. The first MST, M1, will have subtrees S-T and V-U below R, with cost 6 = 2+4, and cost-3 edge T-U not included in M1. But M2 has subtree S-T-U (only) below R, at cost 5.

Improve this answer

Comments

0

Negative. If the idea is to find for every node that contains 'x' a separate path from root to it, and minimize the total cost of the paths, then you can just use simple shortest-path calculation separately for every node starting from the root, and put the paths together.

Some of those shortest paths will not be in the minimum spanning tree, so if this is your goal, the MST solution does not work. MST optimizes the cost of the tree, not the sum of costs of paths from root to the nodes.

If your idea is to find one path that starts from root and traverses through all nodes that contain 'x', then this is the traveling salesman problem and it is an NP-complete optimization problem, i.e. very hard.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.