Finding min-path in undirected graphs.

Finding min-path in undirected graphs.

Post by Bhupen Ahu » Thu, 19 Aug 1993 23:40:03



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

 
 
 

Finding min-path in undirected graphs.

Post by Prashant Saxen » Fri, 20 Aug 1993 05:06:51



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

===================================================================
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.

Post by Benoit Rottembou » Fri, 20 Aug 1993 16:04:33


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.

Post by greg schuweil » Fri, 20 Aug 1993 21:03:05


|>
|> 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

|>
|>

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

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

 
 
 

1. All paths in an undirected graph

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

2. Picking a domain name

3. algorithm to find maximum cliques in k-partite weighted undirected graphs?

4. Excel v 1-2-3

5. algorithm to find maximum cliques in a K-partite undirected graph?

6. Distribution Lists in Messaging Manager

7. Finding cycles in an undirected graph

8. - Newbie Win-OS/2 question

9. finding C4's of an undirected graph

10. Finding a reasonably short path through a growing graph.

11. Auction: Timex Sinclair 1000 (CIB), 1500 (w/Ins), 16K Ram (CIB), 10 Cassettes w/Ins!

12. Expected Max & Min for TSP paths

13. Min-cost Complete Bipartile & Min-cost Network Flow