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).

-sj (for a friend who discovered it)