May 5th, 2010, 10:21 AM  #1 
Newbie Joined: May 2010 Posts: 1 Thanks: 0  Little trick for shortest path
Hey All, A neat trick to calculate the shortest path between vertices of a connected graph. Wanted to share it and validate it's reasoning. Let f(x) be a positive strictly monotone decreasing realvalued function over the +ve naturals (plenty of choices) and f(0) = 0. Say the initial vertex is A and the target is B. a) Assign f(0) to all edges. b) Assign edges incident on A i.e. having A as an end point, the value f(1) and consider the set of end points S1 of these edges which are not A. c) For each member X of S1 repeat the step b) and collect the vertices resulting into a set S2. d) repeat step c) obtaining successive sets Sn till Sn is empty. Obviously n can be at most equal to (number of vertices in the graph  1). Claim: The first time B appears in one of the sets Sm, m is the length of the shortest path. Observations: Each vertex V can appear in an Sm exactly once. This is because at step m when V appears for the first time in S(m), all edges incident on V will be assigned an fvalue. If V is reachable through a longer path it would be through one of the edges incident on V and since each edge already has an fvalue, V will not figure in any set Sj where j > m. Since the graph is connected, each vertex will certainly appear in one of the sets Sn. The initial vertex can be thought to be the the sole member of S0, if you please. To find the shortest path from B to A: 1) Choose the edge incident on B which has the highest fvalue. Consider the endpoint B1 != B of this edge. 2) repeat the step 1) with B1 to get B2, getting successive Bn until you hit A. The sequence of Bi where B0=B upto Bk=A will be a shortest path from B to A. Observation: If there were a shorter path it would be assigned fvalues first by construction and given the highest fvalues possible (remember f is monotone decreasing so that edges getting fvalues first get higher fvalues) along it's edges. Again, you are guaranteed to hit A since the graph is connected. Clean, constructive and quick too. Observations on the number of steps involved: Obs1) You only assign fvalues to edges once. You run into each edge at most twice, since each of it's vertices will appear exactly in one of the sets Sn. The number of operations per edge is at most 3  compare and assign the first time; compare (and dont assign) at most one other time. The number of operations is thus 3xNumber of Edges; besides you could stop assigning fvalues when you encounter B (the target vertex). In case of sparse graphs the Number of Edges is a small multiple of the Number of Vertices  the work is then ord(Number of Vertices). Obs2) The remaining work is in creating each of the sets Sn and involves sorting to guarantee uniqueness of each added vertex. We can eliminate the need for sorting, by attempting to assign fvalues to the incident edges of a vertex V just as we are about to add it to a set Sn, a preassignment of fvalues. This ensures uniqueness of elements in Sn (in cases there are multiple shortest paths leading up to an element in Sn) without the need to sort. This modification only reorganizes the work done in obs1) and does not add to it, since a vertex is chosen for addition to a set Sn only when there is an edge without an assigned fvalue incident on it  preassignment ensures that you still run into an edge exactly twice. Since Sn are a partition of the vertices of the graph, the work involved including the work considered in obs1) is at most 3x(Number of Edges) + (Number of Vertices). For sparse graphs as in obs1) this is ord(Number of Vertices) Obs3) Finally, the actual work of constructing the shortest path is at most equal to the number of edges of the graph (some trivial cases hit the bound). As in obs1), for sparse graphs this is ord(Number of Vertices). The total work done is ord(Number of Vertices). The memory overhead only involves the sets Sn which are a partition of vertices of the graph and fvalues of the edges. The memory overhead is thus = (Number of Vertices) + (Number of Edges). For sparse graphs this overhead is as in obs1) ord(Number of Vertices). Extension to +ve natural edge weights The edge weights so far are all 1, +ve natural edge weights can also be accomodate with a slight extension. In that case, when you run into an edge E with weight K you assign it the fvalue f(m+k) where f(m) is the fvalue upto Sm at which point the edge E is being considered in order to construct S(m+1). The proof works along the same lines as before. We can view this process as breaking an Edge of cost K into a sequence of K virtual edges each of cost 1. Extension to +ve real edge weights If the costs are +ve real then you can come up with a smallenough constant C such that each edge cost is sufficiently wellapproximated by N*C for some N. Then when you run into an edge E with cost K*C you assign the fvalue f(m+K) where f(m) is the fvalue upto Sm at which point the edge E is being considered to construct S(m+1). The proof is same as in the +ve natural weights case. Extension to arbitrary real edge weights For arbitrary weights you would first have to "adjust" all edge weights to be positive by adding a large enough +ve constant K1 to all edge costs and then use the fvalue assignment as for the +ve real weights case. The proof is obviously the same. sj (for a friend who discovered it) 
May 16th, 2010, 10:28 PM  #2 
Newbie Joined: Apr 2009 Posts: 19 Thanks: 0  Re: Little trick for shortest path
Have a look at http://en.wikipedia.org/wiki/Dijkstra's_algorithm 

Tags 
path, shortest, trick 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is integral just trick?  stainburg  Real Analysis  4  June 3rd, 2013 11:05 PM 
trick question  mathkid  Algebra  3  February 25th, 2013 03:51 AM 
Is this Trick Question??  mathkid  Calculus  1  September 22nd, 2012 11:42 AM 
path dependent function with a definite path  aise5668  Real Analysis  3  March 5th, 2012 06:36 PM 
Shortest Path Algorithm  stbrian  Computer Science  0  October 14th, 2007 07:19 PM 