# 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.)

Here is an hint or strategy for the first problem.

Select a path $$P$$ from $$s$$ to $$t$$. Verify that there is perfect matching for the corresponding $$P'$$. Form graph $$Q$$ from $$P$$ by adding one vertex $$u$$ of $$G$$ not in $$P$$ (if there is) and all edges from $$u$$ to vertices in $$P$$. $$P'$$ is extended to $$Q'$$ correspondingly. A bit of reasoning by cases will show the previous perfect matching of $$P'$$ can be extended to a perfect matching of $$Q'$$. Now you can add another vertex, repeatedly.

An answer to the second problem:

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

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.