Very Computer

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

Quote:>GIVEN:
>* Undirected graph
>* Vetrices of the graph are connected by weighted edges
>* ALL the vertices are reachable in the graph
>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>
>Bhupen Ahuja

In addition, there are also several integer programming formulations of
the problem; most of them use heuristics that run pretty well in practice.
See, for instance,
J.E.Beasley, An algorithm for the Steiner problem in graphs. Networks, 14:
  147-159, 1984.
P.Winter, Steiner problem in networks: a survey. Networks, 17:129-167, 1987.

The following reference gives a dynamic programming approach:
S.E.Dreyfus and R.A.Wagner, The Steiner problem in graphs. Networks, 1:195-208,
  1972.

I hope this proves useful to you.

Regards,
prashant

I think what you are asking (if I am reading your question right), that,
given
   G = (V, E, W) with V = {A, B, ..., n} and two vertices in V
   let us say A and you wish to find the shortest path between those
   to vertices.

Then all you need to do is look up E. W. Dijkstra shortest-path slgorithm and
you have your answer.  For computers G is usually represented by an
adjacency (matrix) list structure.

Greg

===========================================================================