An Improved Algorithm for Finding All Pair Shortest Path
Himanshu Garg, Paramjeet Rawat · International Journal of Computer Applications · 2012
Floyd Warshall's Algorithm is a simple and widely used algorithm to compute shortest path between all pairs of vertices in an edge weighted directed graph.It can also be used to detect the presence of negative cycles.Many researchers have given many other approaches for finding all pair shortest path but they reduced the complexity by using complex data structures.In this paper, we suggests a technique for finding shortest path based on Floyd Warshall's algorithm with reduced time complexity and also by not using complex data structures.We present an O(n ) 3 ( ) time algorithm for finding all pair shortest paths.Our proposed algorithm is an improvement on the previous algorithm whose best result was O(n 3 )