I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths but each path has to go through at least one "special vertex" is this even possible or is it hard np
1 Answers
Yes, and you can even use the Floyd–Warshall algorithm as a black box, together with a post-processing step to achieve this.
First, compute the shortest path between every pair of vertices using the Floyd–Warshall algorithm. Then, for each pair of vertices u and v and every special vertex w, compute the sum of the two shortest paths, the one from u to w and the one from w to v. The constrained shortest path from u to v is realized by the special vertex w that minimizes the sum of the u-w path's length and the w-v path's length.
Since the number of special vertices is obviously at most n, the computational complexity of the post-processing step is O(n^3). Because the computational complexity of the Floyd–Warshall algorithm is O(n^3) as well, the total computational complexity of this algorithm is O(n^3).
Related