Google Interview Question
Software AnalystsCountry: India
Interview Type: Written Test
@ piyush kapoor u are right answer is d ... but what does it mean "determining whether there are paths of arbitrarily large weight " please explain..
it means that there is a positive weight cycle. hence, there is no limit to the weight of paths using this cycle repeated times.
I don't really understand what the term "arbitrarily large weight" is implying. However, Floyd-Warshall is an all-pairs shortest paths algorithm. If we are interested in all-pairs shortest paths then we can do better by using Johnson's algorithm whose time complexity is O(V^2 lg V + VE). In contrast, single-source shortest path can be done in O(VE) using Bellman-Ford algorithm. It can handle the scenario where graph contains negative-weight cycles.
If we change positive edge weights into negative edge weights, change negative edge weights into positive edge weights, then this problem is equal to find a path with arbitrarily small weight, there is an algorithm called "BellmanFord" can do this.
If we just have to detect cycles with positive weight then I think DFS should be enough. Just keep storing the nodes visited so far summing the edge weights and when you hit a node that is already visited there is a cycle. Now, just check if the total weight is positive and if it is then we got our answer.
Time complexity: O(n)
Assuming that the weight of a path is simply the sum of edge weights , answer should be (d) , by using any shortest path graph algorithm like floyd warshall .
- Piyush Kapoor September 05, 2013