The shortest_path function finds the shortest path between two nodes (u and v) in a graph g by performing a breadth-first search (BFS) traversal. It returns the path as a list of nodes if found, otherwise returns -1.

Cell 13

def shortest_path(g, u, v):
    """Find shortest path between u and v in g."""
    visited = set()
    from queue import Queue
    q = Queue()
    q.put([u])
    while not q.empty():
        path = q.get()
        if path[-1] == v:
            return path
        visited.add(path[-1])
        for neighbor in g[path[-1]]:
            if not neighbor in visited:
                q.put(path+[neighbor])
    return -1

assert shortest_path({'a': ['a']}, 'a', 'a') == ['a']
assert shortest_path({'a': [], 'b': []}, 'a', 'b') == -1
graph = {'a': ['b'], 'b': ['a', 'c', 'd'], 'c': ['b', 'd', 'e'], 'd': ['b', 'c', 'f'], 
     'e': ['c', 'f', 'g'], 'f': ['d', 'e', 'g'], 'g': ['e', 'f']}
start = 'a'
end = 'g'
assert len(shortest_path(graph, start, end)) == 5
print('All passed!')

python
from collections import deque
from typing import Dict, List

def shortest_path(graph: Dict[str, List[str]], start: str, end: str) -> List[str]:
    """
    Find the shortest path between start and end in the graph.

    Args:
    graph (Dict[str, List[str]]): Adjacency list representation of the graph.
    start (str): Starting node.
    end (str): Ending node.

    Returns:
    List[str]: Shortest path from start to end if exists, -1 otherwise.
    """
    # Initialize visited set and queue for BFS
    visited = set()
    queue = deque([[start]])

    while queue:
        # Dequeue the first path from the queue
        path = queue.popleft()
        # If the end node is reached, return the path
        if path[-1] == end:
            return path
        # Mark the last node as visited
        visited.add(path[-1])
        # Add all unvisited neighbors to the queue
        for neighbor in graph.get(path[-1], []):
            if neighbor not in visited:
                queue.append(list(path) + [neighbor])

    # If no path is found, return -1
    return -1

# Test cases
assert shortest_path({'a': ['a']}, 'a', 'a') == ['a']
assert shortest_path({'a': [], 'b': []}, 'a', 'b') == -1
graph = {
    'a': ['b'],
    'b': ['a', 'c', 'd'],
    'c': ['b', 'd', 'e'],
    'd': ['b', 'c', 'f'],
    'e': ['c', 'f', 'g'],
    'f': ['d', 'e', 'g'],
    'g': ['e', 'f']
}
start = 'a'
end = 'g'
assert len(shortest_path(graph, start, end)) == 5
print('All passed!')

Code Breakdown

Function: shortest_path

Description

Finds the shortest path between two nodes (u and v) in a graph g.

Parameters

• g: a dictionary representing the graph, where each key is a node and its value is a list of neighboring nodes.
• u: the starting node.
• v: the ending node.

Return Value

• If a path from u to v is found, returns the path as a list of nodes.
• If no path is found, returns -1.

Algorithm

1. Initialize an empty set visited to keep track of visited nodes.
2. Create a queue q and add the starting node u as the first path.
3. While the queue is not empty:
   1. Dequeue the next path.
   2. If the last node in the path is the destination v, return the path.
   3. Mark the last node as visited.
   4. For each neighbor of the last node:
      1. If the neighbor has not been visited, create a new path by appending the neighbor to the current path and enqueue it.
4. If the loop completes without finding a path, return -1.

Test Cases

The code includes three test cases:

1. A graph with a self-loop (node 'a' is connected to itself).
2. A graph with no connections between nodes 'a' and 'b'.
3. A graph with multiple nodes and connections, and a path from 'a' to 'g' with a length of 5.