Figure 1: Place non-negative weights on graph (b) so that the new weighted graph is equivalent to the weighted graph in (a) for shortest path problems.