In this post, we’ll see an implementation of shortest path finding in a graph of connected nodes using Python. The shortest path will be found by traversing the graph in breadth first order.

As a related topic, see some common Python programming mistakes.

Let’s consider the following graph. We will traverse it in breadth first order starting from node `0`. Our goal will be to find node `x`.

First, we will traverse the nodes that are directly connected to `0`. Those are `{1, 2, 3}`. If node `x` is part of `{1, 2, 3}`, we stop. If not, we continue traversing the graph.

Next, we consider the set of nodes that are connected to or previous set `{1, 2, 3}`. Those would be `{4, 5, 6}`. Nodes `4` and `5` are connected to node `1` and node `6` is connected to node `3`. We look for node `x` again and then we stop becausre there aren’t any more nodes.

If the graph was larger, we would continue traversing the graph by considering the nodes connected to `{4, 5, 6}` and so on.

See that this order of traversal guarantees that we find the shortest path between node `0` and node `x` because we start by searching the nodes that are one edge away from `node1`, then those that are two edges distant, and so on.

## Graph representation

We will represent our graph as a dictionary, mapping each node to the set of the nodes it is connected to.

For example, let’s consider the following graph.

In this graph, node `4` is connected to nodes `3`, `5`, and `6`. Our `graph` dictionary would then have the following `key: value` pair:

`graph[4] = {3, 5, 6}`

We would have similar `key: value` pairs for each one of the nodes in the graph.

## Shortest path function input and output

### Function input

Our BFS function will take a `graph` dictionary, and two node ids (`node1` and `node2`). For this tutorial, each graph will be identified using integer numbers (`1`, `2`, etc).

### Function output

The function will return a list of nodes that connect `node1` and `node2`, starting with `node1` and including `node2`: `[node1, node_x, node_y, ..., node2]`. This list will be the shortest path between node1 and node2.

If there is more than one possible shortest path, it will return any of them.

In case no path is found, it will return an empty list `[]`.

```from typing import Dict, List

def shortest_path(graph: Dict[int, set], node1: int, node2: int) -> List[int]:
pass```

## Shortest path algorithm

Our algorithm starts by defining a list of possible paths. A “path” is a list of connected nodes. Initially, we have only one “path” possible: `[node1]`, because we start traversing the graph from that node. We also define a set of previously visited nodes to avoid backtracking.

After these initial steps the algorithm does the following:

1. Take the next path from the list of paths.
• If all possible paths have been traversed, stop. No path was found.
2. Set the “current node” to the last node in the current path.
3. Search the goal node, `node2`, between the nodes that are connected to the current node.
• If node2 is connected to the current node, we have found path from node1 to node2. Stop.
4. If node2 isn’t connected to the current node, update the list of paths to traverse.
• Add a new path from `node1` to each one of the connected nodes to traverse next.
5. Go back to step 1.

## Shortest path implementation in Python

Finally, we have the implementation of the shortest path algorithm in Python.

```def shortest_path(graph, node1, node2):
path_list = [[node1]]
path_index = 0
# To keep track of previously visited nodes
previous_nodes = {node1}

if node1 == node2:
return path_list[0]

while path_index < len(path_list):
current_path = path_list[path_index]
last_node = current_path[-1]
next_nodes = graph[last_node]
# Search goal node
if node2 in next_nodes:
current_path.append(node2)
return current_path
for next_node in next_nodes:
if not next_node in previous_nodes:
new_path = current_path[:]
new_path.append(next_node)
path_list.append(new_path)
# To avoid backtracking
# Continue to next path in list
path_index += 1
# No path is found
return []```

We return the trivial path `[node1]` for the case `node1 == node2`.

Variable `path_index` keeps track of the path that we’re currently following. We stop the loop when we reach the end of `path_list`.

At all times, we have a shortest path from `node1` to `last_node`. Based on this path, we can find the path from `node1` to `node2` if `node2` is connected to `last_node`.

The order in which new paths are added to `path_list` guarantees that we traverse the graph in breadth first order.

## Verification

Let’s check our algorithm with the graph shared at the beginning of this post.

We create a `graph` dictionary.

```graph = {}

graph[1] = {2, 5}
graph[2] = {1, 3, 5}
graph[3] = {2, 4}
graph[4] = {3, 5, 6}
graph[5] = {1, 2, 4}
graph[6] = {4}```

Now, let’s find the shortest path from node `1` to node `6`.

```>>> shortest_path(graph, 1, 6)
[1, 5, 4, 6]```
Published inProgramming
Subscribe
Notify of