Given the graph is a directed graph. I want to find the most efficient algorithm. Thanks for help! Maybe we could do it in O(V+E)
Asked
Active
Viewed 225 times
0
-
In the worst case, there would be exponentially many paths, as function of `V`. Traversing them all in `O(V+E)` is a tad optimistic. – Pradhan Dec 27 '14 at 06:43
-
[Floyd-Warshall](http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) to the rescue !... – Rerito Dec 27 '14 at 09:24
-
1@Rerito No. Floyd Warshall is All to all shortest path, while this question is about one two one all paths. – amit Dec 27 '14 at 13:54
1 Answers
1
Consider this graph. The number of paths between s and t is 2^(number of diamonds), where each diamond is a rectangle. Since, 3*(no. of diamonds) + 1 = n, no. of diamonds = (n-1)/3. So, there are 2^(n-1/3) paths between s and t.
This proves that your problem can never be done in linear time.
nishkr
- 99
- 1
- 8