Distance and Shortest Paths in Unweighted Graphs

Now, let’s extend your Graph class with the methods calc_distance and calc_shortest_path. Below is a demonstration of these methods on a particular graph, followed by instructions regarding how to implement them.

>>> graph.calc_distance(0,3)
3
>>> graph.calc_distance(3,5)
3
>>> graph.calc_distance(0,5)
3
>>> graph.calc_distance(4,1)
2
>>> graph.calc_distance(2,4)
False

>>> graph.calc_shortest_path(0,3)
[0, 1, 4, 3]
>>> graph.calc_shortest_path(3,5)
[3, 1, 4, 5]
>>> graph.calc_shortest_path(0,5)
[0, 1, 4, 5]
>>> graph.calc_shortest_path(4,1)
[4, 3, 1]
>>> graph.calc_shortest_path(2,4)
False

The key to implementing these methods is to first create a method Graph.set_distance_and_previous(idx) that does a breadth-first traversal from the node at the given index and sets the attributes node.distance and node.previous for each node encountered during the traversal.

1. Start at the node whose index is idx.
2. In the breadth-first traversal, you'll end up visiting all the children of that node, those children's children, and so on.
3. Whenever you add a child to the queue, set the child's previous attribute to be the parent node that the child is coming from, and set the child's distance attribute to be one more than that parent's distance.
4. When this is all done, each node's distance attribute will represent it's distance from the initial starting node, and each node's previous attribute will represent the node that comes before it if you're traveling to it on the shortest path.

Note that this will require you to write a Node class and create an instance for every node in your graph. It’s best to do this at the very beginning when you first initialize the graph.

When you run Graph.calc_distance(from_idx, to_idx) or Graph.calc_shortest_path(from_idx, to_idx), the first step will always be to run Graph.set_distance_and_previous(from_idx). Once you have the distance and previous attributes set, you can use them to easily compute distances and shortest paths between nodes:

• calc_distance(from_idx, to_idx) - simply return the distance attribute of the "to" node.
• calc_shortest_path(from_idx, to_idx)
  1. Start at the "to" node and repeatedly go to the previous node until you get to the "from" node.
  2. Keep track of all the nodes you visit (this is the shortest path in reverse).
  3. Return the path in order from the "from" node to the "to" node. (You'll have to reverse the reversed path that you found in the previous step.)