Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights 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.)




Related post: Finding shortest paths in undirected graphs with possibly negative edge weights.
An answer to the second problem:

Problem: Each circuit in $S$ must have total weight zero. Why?

Proof: By contradiction.
Suppose that some circuit $C$ in $S$ have nonzero total weight.
Because $G$ has no negative cycles, $C$ has positive total weight.
Note that $C$ does not contain $s$ or $t$. Therefore, the edges of $C$ are all $5$-edge gadgets; see step 2.
Then we can construct another perfert matching on $C$ whose total weight is zero by choosing the middle edge with weight $0$ of each $5$-edge gadgets and the edges between $v$ and $v'$ (for each $v$ in $C$; see step 1) also with weight $0$.
This contradicts the assumption that $M$ is a minimum perfect matching.