I'd really like your help with the following question:
Given a graph G=(V,E) with weights function w: E to R, and a number k. We can assume that there's not a negative cycle in G. I need to find algorithm efficient as possible for finding all the edges of G such that they are part of cycle of weight<=k
I want to split the graph to connected components by DFS and somehow to check each component for the above condition. I can also find the shortest path to each vertex in each component with O(|V||E|) time, but how can I check each cycle of all possible cycles in each component for the best solution?
Thanks a lot!