this case the time complexity for both priority queue versions is (nlog )which is clear improvement over the previous ( algorithm shortest paths floyd' algorithm if we are not only interested in finding the shortest path from one specific vertex to all the othersbut the shortest paths between every pair of verticeswe couldof courseapply dijkstra' algorithm to every starting vertex but there is actually simpler way of doing thisknown as floyd' algorithm this maintains square matrix 'distancewhich contains the overestimates of the shortest paths between every pair of verticesand systematically decreases the overestimates using the same shortcut idea as above if we also wish to keep track of the routes of the shortest pathsrather than just their lengthswe simply introduce second square matrix 'predecessorto keep track of all the 'previous verticesin the algorithm belowwe attempt to decrease the estimate of the distance from each vertex to each vertex by going systematically via each possible vertex to see whether that is shortcutand if it isthe overestimate of the distance is decreased to the smaller overestimateand the predecessor updated/store initial estimates and predecessors for each vertex for each vertex distance[ ][zweight[ ][zpredecessor[ ][zs /improve them by considering all possible shortcuts for each vertex for each vertex for each vertex if distance[ ][ ]+distance[ ][zdistance[ ][zdistance[ ][zdistance[ ][ ]+distance[ ][zpredecessor[ ][zpredecessor[ ][zas with dijkstra' algorithmthis can easily be adapted to the case of non-weighted graphs by assigning suitable weight matrix of and the time complexity here is clearly ( )since it involves three nested for loops of (nthis is the same complexity as running the ( dijkstra' algorithm once for each of the possible starting vertices in generalhoweverfloyd' algorithm will be faster than dijkstra'seven though they are both in the same complexity classbecause the former performs fewer