How do you find the length of the shortest path between two nodes in an unweighted graph?
You use a breadth first search and you keep the distance to each node as you go.
from collections import deque
def shortest_path_length(graph, start, goal):
distance = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal:
return distance[node]
for neighbour in graph[node]:
if neighbour not in distance:
distance[neighbour] = distance[node] + 1
queue.append(neighbour)
return -1
So how does it work? The distance dictionary holds the number of edges from the start to each node that has been reached. The start is at distance zero. When you reach a new neighbour you give it a distance of one more than the current node.
And the reason this gives the shortest path is the order that the search works in. A breadth first search looks at all the nodes one edge away first, then all the nodes two edges away, and so on. So the first time it reaches a node it has found the shortest way to it.
the graph the order of the visits
A: B, C A at distance 0
B: D B and C at distance 1
C: E D and E at distance 2
the goal D is at distance 2
And the complexity is O of n plus m for the time, because every node is reached once and every edge is looked at once, and O of n for the space.
So the rule to remember is this. The distance of a neighbour is one more than the distance of the node you found it from.
The next two questions in this topic show the path counting and the grid version.