## Finding min-path in undirected graphs.

### Finding min-path in undirected graphs.

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

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.

Bhupen Ahuja

### Finding min-path in undirected graphs.

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
>In the example above, I should end up with the following set of edges
>for min-path:
>    <AB>, <BG>, <BC>
>Bhupen Ahuja

===================================================================
What you're talking of is the Steiner tree problem; yes, it is NP-Complete.
However, there are several good approximantion algorithms for the problem
(as well as polynomial, even linear, time algorithms for this problem on
special graph families.) Some good references are:
P.Widmayer, Fast Approximation algorithms for Steiner's problem in graphs.
Habilitation, University of Karlsruhe, Germany.1987.
S.B.Akers, Routing. in M.A.Breuer (ed.), "Design Automation of Digital
Systems. Vol 1: Theory and Techniques", pgs 283-333, Prentice Hall Inc
1972.
T.Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, pgs
83-92, 173-199. Wiley-Teubner Series in Computer Science, 1990.
K.Mehlhorn, A faster algorithm for the Steiner problem in graphs. Info.
Proc.Letters, 27(3):125-128, 1988.
G.F.Sullivan, Approximation algorithms for Steiner Tree Problems, TR 249,
Dept of Computer Science, Yale University, 1982.

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

### Finding min-path in undirected graphs.

the problem you re dealing with is not exactly the Steiner problem, but
can be shown to be NP-complete if you consider that the problem of
finding an hamiltonian path of minimum length, is NP-complete.
I think you should easily find a transformation from this problem to yours.
--
|\
|\| \
|//  )
|\ /  /        /\/\_
|//  /        /. . /
|\ /  /     ___/    |_                 Benoit ROTTEMBOURG
|//  /     (____/    /_/\_
|__|      (_____/ __     >                    ENSTA/ Lei
/| ___  ________ _< \ \__  >
\|| __\| _|_   _/ \\ \___\/
| __\____ | |/ _ \\    >            32, Bd Victor
/||___\_____|___/ \_\\  _>            75015 PARIS
\|____           ____ \|
\   \_________/   /
\   _    _      /

(_   \ (_  _\                    tel:    45526186
|/\|   \/                      fax:    45525587

### Finding min-path in undirected graphs.

|>
|> 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.
|>
|> Bhupen Ahuja

|>
|>

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

Greg

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

Hi,

I am interessted in all path between two nodes of a graph.

Example:

A----B----+
/ \   |    |
| |   |    |
| +-- C ---E
\          |
D---------+

Let's say I want to know all path from node A to node D, which are:
1) A-D
2) A-B-C-E-D
3) A-B-E-D
4) A-C-E-D
5) A-C-B-E-D
As you see a path is defined by the nodes and the sequence of them.

I designed an algorithm which calculates this (or I hope I did, until know not so much
testing) but my method is more or less brute force.

Anyone out who knows if there exists a well known solution or knows a pointer to such
kind of problems?

Thanks
Johann

--
Johann Murauer            |
Utimaco Safe Concept GmbH | Tel:    ++43 (0)732 655 755 - 44
Europaplatz 6             | Fax:    ++43 (0)732 655 755 - 5