chap patterns of algorithms this pointwe can either use the third item or not we can find solution by taking one branch we can find all solutions by following all branches when there is choice all-pairs shortest paths we next consider the problem of finding the shortest distance between all pairs of vertices in the graphcalled the all-pairs shortest-paths problem to be precisefor every uv vcalculate (uvone solution is to run dijkstra' algorithm for finding the single-source shortest path (see section |vtimeseach time computing the shortest path from different start vertex if is sparse (that is|eth(| |)then this is good solutionbecause the total cost will be th(| | | ||elog | |th(| | log | |for the version of dijkstra' algorithm based on priority queues for dense graphthe priority queue version of dijkstra' algorithm yields cost of th(| | log | |)but the version using minvertex yields cost of th(| | another solution that limits processing time to th(| | regardless of the number of edges is known as floyd' algorithm this is another example of dynamic programming the chief problem with solving this problem is organizing the search process so that we do not repeatedly solve the same subproblems define -path from vertex to vertex to be any path whose intermediate vertices (aside from and uall have indices less than -path is defined to be direct edge from to figure illustrates the concept of -paths define dk (vuto be the length of the shortest -path from vertex to vertex assume that we already know the shortest -path from to the shortest ( )path either goes through vertex or it does not if it does go through kthen the best path is the best -path from to followed by the best -path from to otherwisewe should keep the best -path seen before floyd' algorithm simply checks all of the possibilities in triple loop here is the implementation for floyd' algorithm at the end of the algorithmarray stores the all-pairs shortest distances