Returning shortest path using breadth-first search

Question

I have a graph:

graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['bob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []

A function that determines my end node:

def person_is_seller(name):
  return name[-1] == 'm' # thom is the mango seller

And a breadth-first search algorithm:

from collections import deque

def search(name):
  search_queue = deque()
  search_queue += graph[name]
  searched = set()

  while search_queue:
    # print(search_queue)
    person = search_queue.popleft()
    if person not in searched:
      # print(f'Searching {person}')
      if person_is_seller(person):
        return f'{person} is a mango seller'
      else:
        search_queue += graph[person]
        searched.add(person)
  return f'None is a mango seller'

search('you')
# 'thom is a mango seller'

I am wondering if this algorithm can return the shortest path from you to thom?

[you, claire, thom] # as this is the shortest path to thom which is my end node

I checked this answer and it states that it does not let me find the shortest path but the second answer states that it is possible to provide the shortest path, I assume without using Djikstra's algorithm. So I am a bit confused, can I somehow keep track of the previous node, and if the final node is reached provide the shortest path as in the last code snippet or in any other format?

score 2 · Accepted Answer · answered Jan 19 '21 at 23:08

You can make searched a dictionary instead of a set, and then let the value for each key be a backreference to the node where you came from.

When you find the target, you can recover the path by walking back over those backreferences and then return the reverse of that.

Adapted code:

def search(name):
  search_queue = deque()
  search_queue.append((name, None))
  searched = {}  # dict instead of set

  while search_queue:
    # print(search_queue)
    person, prev = search_queue.popleft()
    if person not in searched:
      searched[person] = prev
      # print(f'Searching {person}')
      if person_is_seller(person):
        result = []
        while person is not None:
            result.append(person)
            person = searched[person]
        return result[::-1]
      else:
        search_queue += [(neighbor, person) for neighbor in graph[person]]
  return []

Now the function returns a list. It will have the start and end node when a path is found, so in this case:

['you', 'claire', 'thom']

If no path is found, the result is an empty list.

score 1 · Answer 2 · answered Jan 19 '21 at 23:28

You can use BFS to find the shortest path provided that every edge has the same length. Dykstra's algorithm is necessary when different edges have different weights.

Dykstra's algorithm in its pure form only computes the length of the shortest path. Since you probably want the shortest path itself, you'll want to associate each visited node with the node on the other end of the edge, which is generally done using an associative array (a "dictionary", in Python).

Returning shortest path using breadth-first search

2 Answers2