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

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

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:
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.

GD Star Rating