The Floyd Warshall Algorithm is for solving the All Pairs Longest Path problem???
if no i please provide the proof if yes thn how to implement
Brother, assuming you know the algorithm & both the shortest & longest path problems, let me try to answer your question…
The Floyd Warshall Algorithm fails to solve The All Pairs Longest Path problem.
Explanation:-
A given problem has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.
For example the shortest path problem has following optimal substructure property: If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v. The standard All Pair Shortest Path algorithms like Floyd–Warshall is a typical example of Dynamic Programming.
On the other hand the Longest path problem doesn’t have the Optimal Substructure property. Here by Longest Path we mean longest simple path (path without cycle) between two nodes. Consider the following unweighted graph given in the CLRS book. There are two longest paths from q to t: q → r ->t and q ->s->t. Unlike shortest paths, these longest paths do not have the optimal substructure property. For example, the longest path q->r->t is not a combination of longest path from q to r and longest path from r to t, because the longest path from q to r is q->s->t->r. Courtesy : GeeksforGeeks
3 Likes
thank you guys u always help 