"meeting point" - help with faster algorithm

This is a discussion on "meeting point" - help with faster algorithm within the Tech Board forums, part of the Community Boards category; Hi. My problem is to find the "meeting point" of two given vertices in directed graph. Every vertice in this ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    1

    "meeting point" - help with faster algorithm

    Hi.

    My problem is to find the "meeting point" of two given vertices in directed graph. Every vertice in this graph has only one output edge, so there obviously could be some cycles. We have got for example graph which looks like this:

    1->4
    2->3
    3->5
    4->5
    5->1
    6->1
    7->12
    8->12
    9->9
    10->9
    11->7
    12->1

    And we have to find the distance from the "meeting point" of two given vertices.

    For example:

    The first given vertice is 7 and second - 2. As we can see, the "meeting point" is for example 1, so the distance from 7 to 1 is 2, and from 2 to 1 - 3, so our output is "2 3".

    There are also some restrictions: let the output be "x y", max(x,y) must be minimal, then min(x,y) must be also minimal, and if our output are still ambiguous, our x should be greater.

    If x and y does not exist, we just write "-1 -1".

    My solution is to run through the graph starting from the first given vertice (just like in DFS), saving the number of step in tab[number_of_vertice]. And the same for the second given vertice, but this time instead of saving the number, we check if tab[number_of_vertce] > 0. If true - we can write "tab[number_of_vertce] number_of_actual_step" and finish the algorithm.

    But this is too slow for me, the number of vertices is 500 000, and the number of given pairs of vertices can also reach 500 000, so it looks like a linear-requested problem.

    Could somebody help me with this problem?

    Sorry for my English : )

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,166
    This algorithm is not language specific, so I am moving this thread to Tech Board.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. skipping "else" statement is faster?
    By carlorfeo in forum C++ Programming
    Replies: 13
    Last Post: 03-03-2008, 04:41 AM
  2. Replies: 7
    Last Post: 07-03-2007, 02:49 PM
  3. Which Operation is Faster "=" or "+=" ?
    By thetinman in forum C++ Programming
    Replies: 37
    Last Post: 06-06-2007, 08:29 PM
  4. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 08:25 AM
  5. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 07:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21