Comparison of Floyd-Warshall and Mills Algorithms for Solving All Pairs Shortest Path Problem. Case Study: Sunyani Municipality

Abstract

The Floyd-Warshall and Mill algorithm were used to determine the all pair shortest paths within the Sunyani Municipality so as to compare which of the algorithms runs faster on the computer. The two algorithms were used on a network of 80 nodes with respective edge distances in matrix format as inputs. Matlab codes were generated to run the algorithms. All the two algorithms were able to compute the all pair shortest paths. The running time for the Floyd-Warshall and Mills are 1057.22 and 444.53 ( in seconds ) respectively. The two algorithms computed the shortest path from node 1 (Ohunukurom) to node 80 (Addae Boreso) to be 17.3000 km. Based on this study, it is convenient to conclude that Mills decomposition algorithm runs more faster on a computer than the Floyd-Warshall algorithm.

Keywords: Algorithm, Computations, Node, Running time, Shortest path, infinite


Article Review Status: Published

Pages: 1-17 (Download PDF)

Creative Commons Licence
This work by European American Journals is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License