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