0
$\begingroup$

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the graph. Now I have Q requests , each given a node, return the node that has exactly T distance between the given node.If no such node exists,return the node with largest distance.

BFS for every vertices works, but it sucks when N=1000,and T<=10000. Is there exists a method that works with (N^2 log N) time?

Improve this question
$\endgroup$
6
  • $\begingroup$ oh yea,Q<=100000 and T<=10^9 $\endgroup$
    – user26425
    Commented Sep 12, 2012 at 6:31
  • $\begingroup$ Use a structure with roughly logN entries per node. The ith entry for node v contains (a pointer to) the node at distance 2^i from v. Gerhard "You Figure Out The Rest" Paseman, 2012.09.12 $\endgroup$
    – Gerhard Paseman
    Commented Sep 12, 2012 at 15:36
  • $\begingroup$ thx a lot I think I figure it out! $\endgroup$
    – user26425
    Commented Sep 12, 2012 at 15:41
  • $\begingroup$ If you are cramped for space, but know the nodes in the Q queries and know that the size of that set is small, you can try building up the the database for each node in Q and stop when you have processed the whole list. Worst case involves making the table for the whole graph, but expected behavior can save a lot of time and space. Gerhard "Not To Mention Programming Effort" Paseman, 2012.09.12 $\endgroup$
    – Gerhard Paseman
    Commented Sep 12, 2012 at 15:49
  • $\begingroup$ Also, while this is a nice problem, it is out of scope for this site. For similar questions, try the stackexchange sites for math and computer science. Good Luck. Gerhard "Ask Me About System Design" Paseman, 2012.09.12 $\endgroup$
    – Gerhard Paseman
    Commented Sep 12, 2012 at 15:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .