Two days ago I published my blog entry My Solution to a Question from Jack Edmonds: Reduction of the Shortest Path Problem to the Assignment Problem. Here I will give an example to illustrate how the reduction works.

So let's start with the graph shown in figure 1.

We will construct the bipartite graph shown in figure 2. On the left is the set X, containing copies of all inner nodes and the node t. On the right is the set Y, containing a second copy of all inner nodes and the node s. For each edge (a,b) in the initial graph we add an edge from the node that corresponds to a on the right side to the node that corresponds to b on the left side. In addition to that, we link all pairs, which are the blue horizontal lines.

Next, we assign the right weights to the edges (figure 3). Blue get 0, the other get the weights from the initial graph.

Then we compute a perfect matching with minimal weight that is shown in figure 4 (red).

Starting from s we take alternating edges from the matching (red) and the blue edges until we reach t. The corresponding edges in the initial graph will form the shortest path.

The resulting shortest path is shown in figure 6.