Thread: "meeting point" - help with faster algorithm

  1. #1
    Registered User
    Join Date
    Nov 2011

    "meeting point" - help with faster algorithm


    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:


    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
    This algorithm is not language specific, so I am moving this thread to Tech Board.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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, 01:49 PM
  3. Which Operation is Faster "=" or "+=" ?
    By thetinman in forum C++ Programming
    Replies: 37
    Last Post: 06-06-2007, 07: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