We're sorry but this app doesn't work properly without JavaScript enabled. Please enable it to continue.

This lesson's interactive features are locked, please to keep using them

Edge Relaxation

"Relaxing" an edge means checking if the currently known shortest distance to a node can be improved by following a different edge. If it can, we update its shortest known distance.

Take a look at this graph:

Imagine that we've already found the path from A to C through B, with a total cost of 9. We would have a distances dictionary like this:

distances = {"A": 0, "B": 5, "C": 9}

Then we check the path directly from A to C, which has a cost of 7. Since this is lower than the current known cost of 9, we "relax" the edge and update distances accordingly.

Relaxing a Negative Cycle

Trouble is, if a graph has a negative cycle, we could keep relaxing its edges forever, with the "shortest distance" decreasing every time.

Part of the genius of the Bellman-Ford algorithm is recognizing that the maximum number of edges in any shortest path is n-1, where n is the number of nodes. So if we perform n-1 iterations of edge relaxation, we will definitely have found the shortest paths to all nodes – unless there's a negative cycle.

In Bellman-Ford, we try an nth iteration of edge relaxation, and if any paths continue to shorten, we know a negative cycle exists. We can then raise an exception or return an error value, since the graph is ill-formed.

Assignment

Complete the relax_edge function. This is a key part of the Bellman-Ford algorithm.

Inputs

  • total_distances: a dictionary mapping nodes to their current shortest distance from the source node
  • node_a: the label of the starting node of the edge in question
  • node_b: the label of the ending node of the edge in question
  • dist_a_b: the weight of the edge from node_a to node_b

Outputs

  • True or False, based on whether the edge was relaxed, i.e., whether a new shortest distance to node_b was found. (If so, you'll also update total_distances[node_b]; but only the boolean is returned.)

Steps