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

Bellman-Ford Code

Now let's put the whole algorithm together.

We recently updated the Mappy app to allow food delivery drivers to use it more effectively. Instead of the "cost" of a given route being measured only by driving time, we're also applying a "negative cost" to routes that allow the driver to fuel up. This means Dijkstra's algorithm won't work anymore for finding the shortest path, because some routes will actually have negative values.

Assignment

Complete the bellman_ford function. Its job is to return the shortest distance between two nodes in a graph. The graph will be weighted and directed. If a negative cycle exists in the graph, the function should raise the exception negative cycle detected!.

Inputs

graph: an adjacency list of the nodes in the directed graph (graph[node1][node2] = weight_of_edge)
src: the label of the source node
dest: the label of the destination node

Outputs

distance: an integer representing the length of the shortest route

Algorithm

Create an empty dictionary called distances. The keys will be nodes, and the values will be the "distance so far" to each node from src.
Initialize the distance of the src node to 0 and all other nodes to positive infinity (float("inf")).
Perform the following "relaxing" n-1 times, where n is the number of nodes in the graph:
- For node node1 in the graph:
  - For node1's neighbor node2 in the graph:
    - Call relax_edge, passing in distances, node1, node2, and the weight of the edge from node1 to node2.
Try one more pass of edge relaxation. The first n-1 iterations should have determined all the shortest routes. If we find a new shortest route for any node, there must be a negative cycle. For node node1 in the graph:
- For node1's neighbor node2 in the graph:
  - Call relax_edge, passing in distances, node1, node2, and the weight of the edge from node1 to node2. This time we're interested in the return value. If it returns True, that means the edge could still be relaxed. In that case, raise an exception with the following message:
```
negative cycle detected!
```
Return the shortest distance saved for the dest node.