Hi yall!

Continue if you are interested in Graph-problems...

GIVEN:

* Undirected graph

* Vetrices of the graph are connected by weighted edges

* ALL the vertices are reachable in the graph

(directly or indirectly, i.e.)

GOAL:

To obtain the minimal path (with least accumulative weight)

that connects a set of given vertices. (Is it an NP-complete

problem? If so, I can live with "almost" minimal solution in

case that is feasible.)

EXAMPLE:

Nodes : A, B, C, D, E, F, G, H

Edge/weight: <AB1>, <BC3>, <BG2>, <CD1>, <DE1>, <EF1>,

<FG1>, <GH1>, <HA8>

H -----1----- G -----1----- F -----1----- E

| | |

| | |

8 2 1

| | |

| | |

| | |

A -----1----- B -----3----- C -----1----- D

Now let's say I want to find the best (minimum weight) way of

connecting vertices C, G and A. Its easy to find the min-path

for two vertices in such a graph, but how do find minimal path

for more than 2 vertices in a graph?

BTW, you are allowed to include new vertices to the set <C,G,A>. For

instance, min-path for 'A' & 'G' goes through 'B', so vertex 'B' can

be added to the set of given vertices <C,G,A> if that is useful for

your alogorithm in any way.

In the example above, I should end up with the following set of edges

for min-path:

<AB>, <BG>, <BC>

Any help will be appreciated.

Thanks in advance!

Bhupen Ahuja