Distance and Shortest Paths in Unweighted Graphs

This post is part of a series.

The distance between two nodes in a graph is the fewest number of edges that must be crossed to travel from one node to the other. A path between two nodes is a sequence of nodes that can be traversed to get from one node to the other, traveling along edges. The shortest path is the path with the shortest distance.

Demonstration

Below is a demonstration of distances and shortest paths in a particular graph.

icon



>>> 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

Implementation

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 its 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.)

Exercises

Extend your Graph class to include the methods calc_distance and calc_shortest_path. As always, be sure to write tests.

This post is part of a series.