Teaching Kids Programming – Single Source Shortest Path Algorithm in a Directed Unweighted Graph using Breadth First Search

Teaching Kids Programming: Videos on Data Structures and Algorithms

Shipping and Receiving: Sum of Costs (Shortest Path) of Pairs of Vertex in a Directed Unweighted Graph

You are given a two-dimensional list of integers ports where ports[i] represents the list of ports that port i is connected to. You are also given another two-dimensional list of integers shipments where each list of the form [port_i, port_j] which means there is a shipment request from port_i to port_j.

Given that the cost to ship port_i to port_j is the length of the shortest path from the two ports, return the total cost necessary to send all the shipments. If there’s not a path between two ports, the cost is 0.

Constraints
p ≤ 100 where p is the length of ports
s ≤ 10,000 where s is the length of shipments
Example 1
Input

1 2 3 4 5 6 7 8 9 10

ports = [     [2, 3],     [2],     [1, 0],     [4],     [] ] shipments = [     [2, 4] ]

ports = [
    [2, 3],
    [2],
    [1, 0],
    [4],
    []
]
shipments = [
    [2, 4]
]

Output
3

Single Source Shorted Path Algorithm in a Directed Unweighted Graph using Breadth First Search

Breadth First Search (BFS) Algorithm can be used to compute the Single Source Shortest Path (SSSP) in a directed or undirected Graph where the edges are Unweighted.

The time complexity is O(V+E) and the space complexity is O(V) where V is the number of vertices and E is the number of edges in the undirected graph. We can store the Graph as Adjacency List as we need to enque the vertices in the BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def solve(self, G, paths):
        @cache
        def bfs(i, j):
            q = deque([i])
            seen = set()
            ans = 0
            while q:
                n = len(q)
                ans += 1
                for _ in range(n):
                    cur = q.popleft()
                    if cur == j:
                        return ans - 1
                    for x in G[cur]:
                        if x not in seen:
                            seen.add(x)
                            q.append(x)
            return 0
        return sum(bfs(i, j) for i, j in paths)

class Solution:
    def solve(self, G, paths):
        @cache
        def bfs(i, j):
            q = deque([i])
            seen = set()
            ans = 0
            while q:
                n = len(q)
                ans += 1
                for _ in range(n):
                    cur = q.popleft()
                    if cur == j:
                        return ans - 1
                    for x in G[cur]:
                        if x not in seen:
                            seen.add(x)
                            q.append(x)
            return 0
        return sum(bfs(i, j) for i, j in paths)

There are two ways to deque from BFS Algorithm: Deque one vertex at a time or Deque all vertices of same level/distances. In the former case, we need to enque the cost along with the vertex. In the latter case, we can just use a variable to store the current distance from the source.

The Breadth First Search Algorithm works as follows: First, we enqueue the start/source, then while the queue is not empty, we pop items from the queue and then enque their children nodes/vertices back to the queue. The Queue is a First In First Out (FIFO) data structure.

Shortest Path Algorithms

• Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshal Shortest Path in Simple Undirected Weighted Regular Graph)
• Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph
• Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms
• Teaching Kids Programming – Introduction to Dijkstra Single Source Shortest Path Graph Algorithm
• Teaching Kids Programming – Single Source Shortest Path Algorithm in a Directed Unweighted Graph using Breadth First Search
• Teaching Kids Programming – Floyd Warshal Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)
• Teaching Kids Programming – Uniform Cost Search Algorithm to Solve Single-Source Shortest Path in a Graph
• Teaching Kids Programming – Shortest Path Algorithms by Iterative Deepening Search (IDS), Depth First Search (DFS) or Breadth First Search (BFS) on Undirected Graphs
• Teaching Kids Programming – Finding the Network Delay Time via Floyd-Warshall Shortest Path Algorithm
• Teaching Kids Programming – Distance Between Bus Stops (Shortest Distance in Simple Undirected Weighted Regular Graph)

–EOF (The Ultimate Computing & Technology Blog) —