BFS Shortest Path Between Two Entitiesmedium

BFS Shortest Path Between Two Entities

medium RAG & Retrieval 15 min

NumPy allowed · plain Python earns 10 bonus points

A query retrieves context

Embedding similarity ranks the documents before generation.

Open lesson →

01query

02embed

03retrieve

04context

What is RAG?→ embed →top context

retrieval.md44%

rag-systems.md33%

agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement BFS shortest-path finding over a knowledge graph, the real algorithm behind multi-hop relationship queries ('how is A connected to B').

Task

Implement shortest_path(graph, start, end) using BFS on the directed adjacency list graph. Return the list of node names from start to end inclusive (the shortest such path by edge count). Return [] if no path exists, or [start] if start == end.

Function Signature

shortest_path(graph: dict[str, list[str]], start: str, end: str) -> list[str]

Examples

Example 1: direct connection
Input: graph = {'a': ['b'], 'b': []}
start = 'a'
end = 'b'
Output: ['a', 'b']

Example 2: two-hop path
Input: graph = {'a': ['b'], 'b': ['c'], 'c': []}
start = 'a'
end = 'c'
Output: ['a', 'b', 'c']

Example 3: no path exists
Input: graph = {'a': ['b'], 'b': [], 'c': []}
start = 'a'
end = 'c'
Output: []

Constraints

graph maps node -> list of neighbor nodes

Python3Saved ✓

from collections import deque

def shortest_path(graph, start, end):

# Your implementation here

pass

Case 1: direct connection

Input: graph = {'a': ['b'], 'b': []}
start = 'a'
end = 'b'

Expected: ['a', 'b']

Case 2: two-hop path

Input: graph = {'a': ['b'], 'b': ['c'], 'c': []}
start = 'a'
end = 'c'

Expected: ['a', 'b', 'c']

Case 3: no path exists

Input: graph = {'a': ['b'], 'b': [], 'c': []}
start = 'a'
end = 'c'

Expected: []