User:Lonlypiano/sandbox

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. 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. 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. Since |S|=2 now, the algorithm change to Spira's algorithm.D[B]+c(B,T)=6>D[S]+c(S,A)=3,according to Spira's algorithm,A is chosen. Then A is find out to be out of S set,add A to S set and because all vertices connected to s has been labeled,no next candidate edge can be advance, the algorithm go to next iteration.

The algorithm search for all the vertex in the Set S and find out the shortest useful candidate edge. 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. We identify B to be labeled and we change to Spira’s algorithm to indentify A and T.

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