Shortest cycle in an undirected unweighted graph , can we do better ? (Graph problem 13)

help
, , ,
1

I wanna find out the length of shortes cycle in graph , one approach is just do brute force , but time complexity is N2 ,

Question : “Breadth First Search - Eolymp”

After solving above problem , I google but here what i found -
GFG article : “Shortest cycle in an undirected unweighted graph - GeeksforGeeks”

My more optimised solution : “hjaBe1 - Online C++0x Compiler & Debugging Tool - Ideone.com”

But as I said it is still N2 can we do something better , by using concept of LCA or something else ?

@galencolin @ssjgz @aneee004 @everule1 @spaanse

2

any idea ? @ssjgz

3

Just had a quick google, and can’t seem to find anything better :man_shrugging:

1 Like
4

one more doubt -

“Shortest Path with even number of Edges from Source to Destination - GeeksforGeeks”

see in this we have to find the shortest even length path between source and destination,

But this above approach seems wrong, the test case which author takes when i take source as 1 and destination 2 then the code gives output 13 but it should be -1 .