Zunayed Ali Morsalin Home

Shortest path between nodes in a graph

Tags: graphs

Problem statement

Given a unweighted graph, a source and a destination, find the shortest path from source to destination in the graph


Before we start this problem let’s take a quick look on how we would traverse a graph. In this case we can use a Bread first approach so we can determine the shortest distance.


def bfs(start):
    visited = set()
    q = deque()


    while q:
        cur = q.popleft() # fifo

        for n in cur.neighbors:
            if (n.val not in visited):

Now that we know how to traverse lets try to figure out how to find a specific node and also the shortest path. Consider the following graph. Lets say we want to get to Node(5) from Node(1). We see there are a few different paths but only 1 that is 2 hops away. We can modify our existing bfs code to do a check for the cur.val == target.val and find the node we’re looking for but that doesn’t give us a way to get the path back to the starting point. To do that we can save the previous connected node for the current node. This way we can traverse back to the start similar to a linked list.


Once we have a dictionary of back references we can iterate through from the cur value while looking up values


Putting it all together -

from collections import deque

def shortest_path(start, target):
    q = deque()
    back_ref = {}   # replaces seen from normal bfs
    back_ref[start.val] = None

    while q:
        cur = q.popleft()
        if cur.val == target.val:

        for n in cur.neighbors:
            if n.val not in back_ref:
                back_ref[n.val] = cur

    # no target found
    if target.val not in back_ref:
        return []

    # now we take cur and go backwards
    output = []
    cur = target

    # Will stop at the start since the
    # back ref was set to None
    while cur:
        cur = back_ref[cur.val]

    # reverse order
    return output