|
2 | corrected spelling of "mentioned" | ||
|
Oh, and there is another way, with the BFS you mentionnedmentioned. Iteratively, do a BFS from each node. By slightly modifying the BFS algorithm, you can instead of computing the distances from your source vertex to any other, remember the number of shortest paths from your source vertex to any other. If there is a vertex at distance two which has at least 2 shortest paths to the source vertex, you have found your $C_4$. That's $O(n^3)$. |
||||
|
|
1 |
|
||
|
Oh, and there is another way, with the BFS you mentionned. Iteratively, do a BFS from each node. By slightly modifying the BFS algorithm, you can instead of computing the distances from your source vertex to any other, remember the number of shortest paths from your source vertex to any other. If there is a vertex at distance two which has at least 2 shortest paths to the source vertex, you have found your $C_4$. That's $O(n^3)$. |
||||
