In 1985, Moffat-Takaoka (MT) algorithm was developed to solve the all pairs shortest path (APSP) problem. This algorithm manages to get time complexity of O(n² log n) expected time when the end-point independent model of probabilistic assumption is used. However, the use of a critical point introduced in this algorithm has made the implementation of this algorithm quite complicated and the running time of this algorithm is difficult to analyze. Therefore, this study introduces a new deterministic algorithm for the APSP that provides an alternative to the existing MT algorithm. The major advantages of this approach compared to the MT algorithm are its simplicity, intuitive appeal and ease of analysis. Moreover, the algorithm was shown to be efficient as the expected running time is the same O(n² log n). Performance of a good algorithm depends on the data structure used to speed up the operations needed by the algorithm such as insert, delete-min and decrease-key operations. In this study, two new data structures have been implemented, namely quaternary and dimensional heaps. In the experiment carried out, the quaternary heap that employed similar concept with the trinomial heap with a special insertion cache function performed better than the trinomial heap when the number of n vertices was small. Likewise, the dimensional heap data structure executed the decrease-key operation efficiently by maintaining the thinnest structure possible through the use of thin and thick edges, far surpassing the existing binary, Fibonacci and 2-3 heaps data structures when a special acyclic graph was used. Taken together all these promising findings, a new improved algorithm running on a good data structure can be implemented to enhance the computing accuracy and speed of todays computing machines.