Negative-weight cycles Recall: If a graph G=(V, E) contains a negative weight cycle then some shortest paths may not exist Example: <0 Bellman-Ford algorithm: Finds all shortest-pat lengths from a sources e y to all ve yor determines that a negative-weight cycle exists c 2001 by Charles E Leiserson Introduction to Algorithms Day 31 L18.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.2 Negative-weight cycles Recall: If a graph G = (V, E) contains a negative￾weight cycle, then some shortest paths may not exist. Example: uu vv … < 0 Bellman-Ford algorithm: Finds all shortest-path lengths from a source s ∈ V to all v ∈ V or determines that a negative-weight cycle exists