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

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

1041 words

**Last Post**: How to Delete/Remove Kubernetes – Azure Arc using CLI without kubeconfig or connected to cluster? **Next Post**: Teaching Kids Programming – Minmax Dynamic Programming Algorithm (Game of Picking Numbers at Two Ends)

Source: Internet