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.
- Start at the node whose index is
idx
. - In the breadth-first traversal, you'll end up visiting all the children of that node, those children's children, and so on.
- 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'sdistance
attribute to be one more than that parent's distance. - When this is all done, each node's
distance
attribute will represent it's distance from the initial starting node, and each node'sprevious
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 thedistance
attribute of the "to" node.calc_shortest_path(from_idx, to_idx)
- Start at the "to" node and repeatedly go to the previous node until you get to the "from" node.
- Keep track of all the nodes you visit (this is the shortest path in reverse).
- 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.)
Leave a Comment