User:Lonlypiano/Moffat-Takaoka algorithm

In computer science,the Moffat-Takaoka algorithm is a algorithm that computes all pair shortest path in a non-negatively weighted complete graph. It was first published by ALISTAIR MOFFAT and TADAO TAKAOKA in 1987. The algorithm combined both Dantzig’s and Spira’s algorithm.

Algorithm

For a graph with n nodes,choose randomly a source vertex to start with Dantzig’s algorithm to label vertices, but using a heap priority queue to store candidate vertices, until n-n/log n vertices are labelled. We defined an set S to store the labeled vertices.In the beginning only the start vertex is in S.

For any vertex c and u, D[c] is the distance from s to c, c(c,u) is the cost from c to u.Initially,D[s]=0.The Dantzig’s algorithm search for all the vertex in the Set S and find out the shortest useful candidate edge (c,u),assume c is in S and u is out of S. An edge is a useful candidate if one of the two vertices formed the edge is inside S and the other is outside S, otherwise it is useless. u is then add to S,means u is labeled.

The algorithm then searched all useless edges and advance these edges to next shortest useful edges. For example, (c,u) is useless and there is (c,k) where c(c,k)>c(c,u) then (c,k) becomes the key for c. Each vertex has a key that refers to its shortest edges from it.For example vertex c has edges (c,k)>(c,u), then (c,u) is the key for c until (c,u) becomes useless, then the algorithm advanced to (c,k). Each vertex has a list stores all its outgoing edges in a cost increasing order.

If |S|<=n-n/logn,the algorithm iterate above steps.Else,the algorithm then starts to use Spira’s algorithm to do the remaining labeling. The point when the labeled vertices reached n-n/log n is called as a critical point.

Spira’s algorithm also choose the shortest edges.But it does not has the concept of useful and useless vertex. Instead, in every iteration, the algorithm check the shortest candidates edge. If the endpoint of the edge is out of S,then it is added to S. Then the algorithm advance the key to next shortest edge.If the endpoint of the edge is in S,it will also be advanced. The algorithm iterates until all n nodes are found.

With changing Dantzig’s algorithm to Spira’s algorithm at the critical point, after applying the above steps for all n nodes in the graph Moffat-Takaoka’s algorithm can run in average O(n² log n).

Example

In the example graph, there are 4 vertices. So the critical point will be n-n/logn namely 4-4/log4 =2 . We use s to be the first start vertex. To start, use Dantzig’s algorithm. In the beginning, the only vertex in S set is the s vertex in the example. So the shortest useful edge is 2. Then B is then added to S. The algorithm now searched all useless candidate and advance to the next candidate.So the key for s become (S,A). Since |S|=2 now, the algorithm change to Spira's algorithm.D[B]+c(B,A)=9>D[B]+c(B,T)=6>D[S]+c(S,A)=3,according to Spira's algorithm,A is the shortest candidate at this stage. Then A is find out to be out of S set,add A to S set. Because all vertices connected to s has been labeled,no next candidate edge from can be advance, the algorithm go to next iteration.

Complexity

To implement single-source shortest path in both Dantzig’s and Spira’s algorithm takes O(nlog n)time , because there are n vertices, so it will take O(n²logn) running time in total.

Pseudocode

Function Moffat_Takaoka (s);

S = {s}; D[s] = 0; V= all vertices;

candidates set K= {(s, t)}, where D[t] is the shortest path value from s;

call Dantzig (n-n/log n,V);

U= V-S; //U is set of all unlabeled vertices

call Spira (n,U).

End function

Proof of correctness

Only if the algorithm start from 1 labeled vertex to n-n/logn labeled vertices, Dantzig’s algorithm can run in O(nlogn). After the critical point, there will be too much candidates become useless.

Variations

The edge list is set to ascending order. At critical point, the algorithm change to use Spira’s algorithm.

Related algorithms

The MT algorithm is faster than Floyd-Warshall algorithm, but requiring non-negative weights while FW does not.

To solve all pairs shortest path Dijkstra algorithm can be called for n times to achieve the goal,beside the running time is different from MT algorithm, the Dijkstra’s algorithm is designed for single-source shortest path problem.

Fredman’s algorithm,developed by M. L. Fredman ,uses efficient distance-matrix multiplication techniques and has O(n³((log log n)/log n)^1/3).

Karger Koller Phillips algorithm has a running time of O(nm*+n²logn).

Tadao Takaoka’s simplified Moffat-Takaoka’s algorithm. The running time is still the same with Moffat-Takaoka’s algorithm, but the new algorithm is more efficient.

References

On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka by Kurt Mehlhorn and Volker Priebe

AN ALL PAIRS SHORTEST PATH ALGORITHM WITH EXPECTED TIME O(n2 log n) by Alistair Moffat and Tadao Takaoka

A simplified algorithm for the all pairs shortest path problem with O(n2 log n) expected time by Tadao Takaoka