Well-definedness of shortest paths If a graph G contains a negative-weight cycle then some shortest paths may not exist Example: <0 c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17.6© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.6 Well-definedness of shortest paths If a graph G contains a negative-weight cycle, then some shortest paths may not exist. Example: uu vv … < 0