Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for undirected graphs with negative-weight edges but no negative cycles.
I have two problems in understanding this algorithm:
- In step 3, why must $G'$ have perfect matchings so that we can apply Edmonds' Minimum Weight Perfect Matching Algorithm to $G'$?
- In step 4, why must each circuit in $S$ have total weight $0$?
(A possible argument is like this: Because there are no negative cycles, we only need to show that each circuit in $S$ cannot have positive total weight. Maybe this can be proved by contradiction. Suppose that some circuit in $S$ have positive total weight, we need to show that $M$ is not a mimimum weight perfect matching or this cannot be a circuit. However, I failed to reach a contradiction.)