FLOYD’S SHORTEST-PATH ALGORITHM THEORY

Aini Hayati binti Anuar #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 ainihayatianuar@gmail.com
2 faidzms@ieee.org

 
Abstract— These studies are parallel algorithms for the Floyd’s shortest-path algorithm theory for solving the all pairs shortest-path problem which can be categorized into two cases. For a better understanding, we would like to explain the algorithm theory which has the most unfavorable scenario runtime of O( ) for graphs with n vertices. Researchers have put a lot of effort in order to improve the algorithms and at the same time, developing the other algorithms also. Based on these studies, the important, advantages and disadvantages of the Floyd’s shortest-path algorithm theory have been identified.
Keywords: Parallel Algorithm, Shortest-Path Algorithm, Floyd’s



REFERENCES

[1]	F. Glover, D. Klingman, and N. Phillips, "A new polynomially bounded shortest path algorithm," Operations Research, vol. 33, pp. 65-73, 1985.

[2]	A. Aini and A. Salehipour, "Speeding up the Floyd–Warshall algorithm for the cycled shortest path problem," Applied Mathematics Letters, vol. 25, pp. 1-5, 2012.

[3]	S. Hougardy, "The Floyd–Warshall algorithm on graphs with negative cycles," Information Processing Letters, vol. 110, pp. 279-281, 2010.

[4]	G. Gallo and S. Pallottino, "Shortest path algorithms," Annals of Operations Research, vol. 13, pp. 1-79, 1988.

[5]	B. V. Cherkassky, A. V. Goldberg, and T. Radzik, "Shortest paths algorithms: Theory and experimental evaluation," Mathematical programming, vol. 73, pp. 129-174, 1996.

[6]	D. B. Johnson, "Efficient algorithms for shortest paths in sparse networks," Journal of the ACM (JACM), vol. 24, pp. 1-13, 1977.

[7]	T. M. Chan, "All-pairs shortest paths with real weights in O (n 3/log n) time," Algorithmica, vol. 50, pp. 236-243, 2008.

[8]	T. M. Chan, "More algorithms for all-pairs shortest paths in weighted graphs," SIAM Journal on Computing, vol. 39, pp. 2075-2089, 2010.

[9]	M. L. Fredman, "New bounds on the complexity of the shortest path problem," SIAM Journal on Computing, vol. 5, pp. 83-89, 1976.

[10]	Y. Han, "A note of an O (n3/logn) time algorithm for all pairs shortest paths," Information Processing Letters, vol. 105, pp. 114-116, 2008.

[11]	Y. Han, "An O (n 3 (log log n/log n) 5/4) Time Algorithm for All Pairs Shortest Path," Algorithmica, vol. 51, pp. 428-434, 2008.

[12]	Y. Han and T. Takaoka, "An O (n 3 log log n/log 2 n) time algorithm for all pairs shortest paths," 2009.

[13]	T. Takaoka, "A new upper bound on the complexity of the all pairs shortest path problem," in Graph-Theoretic Concepts in Computer Science, 1991, pp. 209-213.

[14]	T. Takaoka, "A faster algorithm for the all-pairs shortest path problem and its application," in Computing and Combinatorics, ed: Springer, 2004, pp. 278-289.

[15]	T. Takaoka, "An O (n3loglogn/logn) time algorithm for the all-pairs shortest path problem," Information Processing Letters, vol. 96, pp. 155-161, 2005.

[16]	U. Zwick, "A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths," Algorithmica, vol. 46, pp. 181-192, 2006.

[17]	S. Pettie, "A new approach to all-pairs shortest paths on real-weighted graphs," Theoretical Computer Science, vol. 312, pp. 47-74, 2004.

[18]	E. W. Weisstein, "Floyd-Warshall Algorithm," 2008.

[19]	S. Sanan, L. jain, and B. Kappor, "Shortest Path Algorithm," International Journal of Application or Innovation in Engineering & Management (IJAIEM), vol. 2, July 2013.

[20]	R. Bellman, "Dynamic programming and Lagrange multipliers," Proceedings of the National Academy of Sciences, vol. 42, pp. 767-769, 1956.

[21]	R. W. Floyd, "Algorithm 97: shortest path," Communications of the ACM, vol. 5, p. 345, 1962.