# Finding an augmenting path or cycle in weighted graph

Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $$M$$, which may or may not be max weight. I know that $$M$$ will be max weight if and only if the graph does not contain an $$M$$-augmenting path or cycle. But is there an efficient way to compute such an object? In the unweighted case, there is an efficient method for finding an augmenting path by doing a modified breadth-first-search (where for every other 'layer' of the search you take the unique matched edge available, assuming it exists), but I don't really see how this would generalize to the weighted case.

Would someone be able to verify whether or not an efficient algorithm for finding such an augmenting path/cycle exists, and possibly explain a sketch of how this works (assuming it is pretty technical) or give a reference of where to find an explanation? Any assistance would be appreciated.