My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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 real-valued 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 f-value. 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 f-value, 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 f-value. Consider the end-point 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 f-values first by construction and given the highest f-values possible (remember f is monotone decreasing so that edges getting f-values first get higher f-values) 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 f-values 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 f-values 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 f-values to the incident edges of a vertex V just as we are about to add it to a set Sn, a pre-assignment of f-values. 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 re-organizes 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 f-value incident on it - pre-assignment 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 f-values 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 f-value f(m+k) where f(m) is the f-value 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 small-enough constant C such that each edge cost is sufficiently well-approximated by N*C for some N. Then when you run into an edge E with cost K*C you assign the f-value f(m+K) where f(m) is the f-value 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 f-value assignment as for the +ve real weights case. The proof is obviously the same.

-sj (for a friend who discovered it)
ssjssujs is offline  
 
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
hkoehler is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2019 My Math Forum. All rights reserved.