Getting TLE error
BFS - Shortest Path TLE
Hey @koshimagoyal97,
You would need to rewrite your code a bit. Instead of Arraylist, I suggest use Array of size n+1 to store the costs with initial values as -1. Also, because you need to find distance from a given node only and your code will become a little more simpler. And, could you please tell me what is int dest = 3 in your code also why is its value 3?
dest=3 is the destination and for the time being i fixed the destination to check whether my code is running for the same or not.
Do I need to use Array everywhere in the code instead of ArrayList?
Hi @koshimagoyal97,
Yes replace array with Arraylist and you don’t need an additional arraylist called cost_list. Use the array to find only the shortest path and multiply your answer by 6 when you are printing.
Okay. So, make your code dynamic by putting appropriate values in dest.
And, share with me your code after you’ve implemented this.
Hi @koshimagoyal97,
You need to return an array from the shortestPath function. In the shortest path function, create a distance array of size number of nodes +1. And initially fill the Array with -1 as values. Now make a Hashset for visited nodes and a queue for nodes that you need to visit.
Now to this queue add the start node and put the value of start index in the distance array as 0.
Now all you need to do is start a while loop such that the size of queue is >0. Now pop the current node and add it to our hashset of visited node. And start a for loop for the current node and visit all the neighbors while updating the distance array.
Hi @koshimagoyal97,
Since you are only adding vertices which the user inputs to store neighbors, if the start node is something which is different than the nodes mentioned in the input. It will give you a nullpointer exception.
For example if the input is:
1
4 2
1 2
2 4
3
This input will give you a null pointer exception. The answer should be -1 -1 -1.
To tackle this add the following code snippet after taking n and m as inputs.
for(int i = 1;i<n+1;i++)
{
bfs.addVertex(i);
}
Also, for the input
1
4 3
1 2
2 3
3 4
1
you are getting answer 6 -1 -1. The correct answer should be 6 12 18.
This is because you only updating your code by only 6.
https://ide.codingblocks.com/s/146935 I have corrected your code for possible errors. I have only made slight changes to it. You can compare and feel free to revert back to me for any doubts.
Thanks
1 Like