Shortest Path in Unweighted Graphs

Run a breadth first search from the start node, recording the distance to each node as you discover it. The distance of a neighbour is one more than the distance of the node that found it, and the answer for the goal falls out of the search.

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


graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
print(shortest_path_length(graph, "A", "E"))

The output is 2. The route A to C to E has two edges, while the route through B and D has three, so the shorter one wins.

The mechanism is that breadth first search processes nodes in order of their distance from the start, so the first time a node is discovered it has been reached by a shortest path. The distance map doubles as the visited set, which is why there is no separate visited structure.

The trade-off to name is that this only works because every edge has the same cost. With weighted edges you need Dijkstra or a breadth first search over the expanded state space, and the ordering guarantee disappears. The other detail is that the search can stop as soon as the goal is reached, but if you also want the distances to every other node you have to let it run to the end.

Keep a distance map and a second map counting the ways to reach each node at that distance. When you discover a neighbour for the first time you copy the count of the node you came from, and when you meet a neighbour that is already at the next distance you add to its count.

from collections import deque


def count_shortest_paths(graph, start, goal):
    distance = {start: 0}
    ways = {start: 1}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in distance:
                distance[neighbour] = distance[node] + 1
                ways[neighbour] = ways[node]
                queue.append(neighbour)
            elif distance[neighbour] == distance[node] + 1:
                ways[neighbour] += ways[node]
    return ways.get(goal, 0)


graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
print(count_shortest_paths(graph, "A", "D"))

The output is 2. There are two shortest routes to D, one through B and one through C, and both have two edges.

The mechanism is that the count for a node is the sum of the counts of all its predecessors that sit exactly one level closer to the start. Because breadth first search processes nodes in distance order, all of those predecessors have already been counted by the time the node is dequeued, so the final count is correct.

The trade-off to name is that the counts can grow very large, so in a graph with many equally short routes the numbers can exceed what a fixed width integer holds. The other subtlety is that the addition branch only applies when the neighbour is already at exactly the next distance. A neighbour at a shorter distance is ignored, and a neighbour at a longer distance cannot happen because the search would have discovered it earlier.

Treat the grid as a graph where each open cell is connected to its open neighbours, and run breadth first search from the start cell. The distance to each cell is the number of steps taken, and the answer is the distance to the bottom right cell.

from collections import deque


def shortest_path_in_grid(grid):
    rows, cols = len(grid), len(grid[0])
    distance = [[-1] * cols for _ in range(rows)]
    distance[0][0] = 0
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if r == rows - 1 and c == cols - 1:
            return distance[r][c]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and distance[nr][nc] == -1:
                    distance[nr][nc] = distance[r][c] + 1
                    queue.append((nr, nc))
    return -1


grid = [[0, 0, 0], [1, 1, 0], [0, 0, 0]]
print(shortest_path_in_grid(grid))

The output is 4. The blocked cells in the middle row force the path along the top row and then down the right hand column, which takes four moves to reach the bottom right corner.

The mechanism is the same breadth first search, with the grid providing the adjacency on the fly. Each cell has at most four neighbours, so no adjacency structure has to be built, and the distance grid doubles as the visited structure.

The trade-off to name is the memory of the distance grid, which is proportional to the number of cells, and the fact that a breadth first search explores every reachable cell even though you only need the goal. The early return when the goal is dequeued saves work, and it is safe because breadth first search reaches the goal by a shortest path. If the grid allowed diagonal moves you would add four more directions, and if the cells had different costs you would need Dijkstra instead.