BFS - Shortest Path TLE

#1


TLE in test cases. Please help with this.

#2

@koshimagoyal97
Sorry for the late reply.
Current complexity of your code:O(t*(V+E)V),where t=test cases.
V=Vertices and E =number of Edges.
Your function printShortDist in itself is making (V+E)(V) computations.
Looking at the constraints Anything over 10^8 will give TLE.
Hint:Try to use simple DFS which will take only V+E computations per test case and revert back here with the modified code,we will be glad to help you.
Hit like if i provided a satisfactory explanation to the problem.

1 Like
#3

@mailmeanmolbansal
But when BFS is mentioned in the question then why we are using DFS??

#4

@koshimagoyal97
Thanks for correcting me,Its BFS.

#5

@mailmeanmolbansal
I have made changes in the code but I am not able to understand how to change destination. If I will use the loop then again the complexity will be increased. So how can I solve this issue?

#6

@koshimagoyal97
Its just like a tree we have to simple iterate over n,starting from 1 to n and find shortest distance of reaching from start node to every other node.
For e.g. Consider n=6 m=3
3 4
3 2
2 5
Start node=3;
Graph looks like:
4 connected with 3
3 connected with 2
2 connected with 5
Now lets see an approach:
There are 6 nodes:
Part 1:Clearly 1 6 aren’t reachable.
So while taking input use a HashSet or Set and put every given vertex in it.
As 1 and 6 aren’t given.So at the end of the input HashSet will not contain any 1 and 6(Use .contains of Hashset), hence these two will have dist as -1.
Part 2:
Now comes 4 3 2 5
Iterating from 1 to n,if(hashset.contains(v)) // find distance from the start node given to n.
Do this for all 4 3 2 5.
else syso("-1");//hashset doesn’t contains these nodes or vertices.
Time Complexity:
Searching in a Tree using BFS,will take from a node to another node and shortest path a TC of N,no of nodes per test case.
Output: 6 6 12 -1 -1 Start node=3.
You yourself Come up with updated code,as directly proving the code won’t help much.
Hit like,if you are satisfied.

#7

@mailmeanmolbansal
You don’t get my question. Please check my previous code and I understood what is the approach but I am asking when I iterate 1 to n then I have to use for loop again then it will result in complexity O(t*(V+E)V) but I want to reduce the complexity so how can we achieve that. Either I will be using for loop in BFS code only or outer the BFS and call BFS in that loop then it will ultimately result in same complexity.
If some edges which aren’t present in graph that can be done directly but for more than 1 vertice we need to use loop.
I am not asking for the solution just help me out with my queries that’s all because I am not good at Graphs.