Consider a program that takes as input a simple graph G, two points A and B and prints all the shortest paths between the two vertices A and B.
If the number of vertices of the G is n , then what is the best achievable worst case runtime complexity of such a program?
O(n 2^n)
INCORRECT
O(\frac{n!}{n})
CORRECT ANSWER
O(\frac{n!}{n^2})
O(n^2 2^n)
Please explian to me this
@Somasree
sry , dont know how they have comeup with this formula.
if they have given any explanation then pls share it with me
ok so the shortest path in worst case is of size n (ie all vertices are in single line)
since 2 vertices are fixed , we can permute remaining n-2 vertices and compute all possible path (n-2)!.
time to print one path is n-1. so final solution cost will be (n-2)! * (n-1) = (n-1)!
that why the solution is (n-1)!== n!/n
ok thank u.I have understood
Please tell me what are Back edges in a undirected graph
pls create another thread
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
