CODEWITHSUNDEEP
time-complexityshortest-pathbreadth-first-search
Lei Chen
Lei Chen

Reputation: 719

Finding Shortest Path using BFS search on a Undirected Graph, knowing the length of the SP

I was asked an interview question today and I was not able to solve at that time.

The question is to get the minimum time complexity of finding the shortest path from node S to node T in a graph G where:

  1. G is undirected and unweighted
  2. The connection factor of G is given as B
  3. The length of shortest path from S to T is given as K

The first thing I thought was that in general case, the BFS is fastest way to get the SP from S to T, in O(V+E) time. Then how can we use the B and K to reduce the time. I'm not sure what a connection factor is, so I asked the interviewer, then he told me that it is on average a node has B edges with other nodes. So I was thinking that if K = 1, then the time complexity should be O(B). But wait, it is "on average", which means it could still be O(E+V), where the graph is a like a star and all other nodes are connected to S.

If we assume that the B is a strict up limit. Then the first round of BFS is O(B), and the second is O(B*B), and so on, like a tree. Some of the nodes in the lower layer may be already visited in the previous round therefore should not be added. Still, the worst scenario is that the graph is huge and none of the node has been visited. And the time complexity is

O(B) + O(B^2) + O(B^3) ... O(B^K)

Using the sum of Geometric Series, the sum is O(B(1-B^K)/(1-B)). But this SUM should not exceed V+E.

So, is the time complexity is O(Min(SUM, V+E))?

I have no idea how to correctly solve this problem. Any help is appreciated.

Upvotes: 1

Views: 1283

Answers (1)

toyeah
toyeah

Reputation: 26

Your analysis seems correct. Please refer to the following references.

http://axon.cs.byu.edu/~martinez/classes/312/Slides/Paths.pdf https://courses.engr.illinois.edu/cs473/sp2011/lectures/03_class.pdf

Upvotes: 1

Related Questions