Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph | ninjasquad

**Teaching Kids Programming**: Videos on **Data Structures and Algorithms**

### Shipping and Receiving – Sum of Costs between Pair of Vertices in 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

### Depth First Search Algorithm on Unweighted Graph

The Depth First Search Algorithm (DFS) does not always find the optimal solutions unless we exhaust searching the entire Graph. The time complexity of the DFS is O(V+E) because we have to search all the vertices and edges. The following is the Recursive DFS to find the shortest path between a pair of vertices. The DFS to compute shortest paths only works in an unweighted Graph (or equal weights).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution: def solve(self, G, paths): @cache def dfs(i, j): def f(i, j, seen = set()): if i == j: return 0 if i in seen: return inf seen.add(i) ans = inf for x in G[i]: ans = min(ans, f(x, j, seen) + 1) seen.remove(i) return ans d = f(i, j, set()) return d if d < inf else 0 return sum(dfs(i, j) for i, j in paths) |

class Solution: def solve(self, G, paths): @cache def dfs(i, j): def f(i, j, seen = set()): if i == j: return 0 if i in seen: return inf seen.add(i) ans = inf for x in G[i]: ans = min(ans, f(x, j, seen) + 1) seen.remove(i) return ans d = f(i, j, set()) return d if d < inf else 0 return sum(dfs(i, j) for i, j in paths)

For a Graph, we have to keep tracking of the vertices that have been visited so that we don’t end up visiting them again and again. This is done via a hash set.

### Depth Limit Search Algorithm on Unweighted Graph

The DLS (Depth Limit Search) Algorithm is based on Depth First Search Algorithm and with an additional requirement of a given max depth. The nodes that are beyond the depth d are ignored. So the DLS don’t end up travering a deep branch.

1 2 3 4 5 6 7 8 9 10 11 12 |
def dls(s, e, d, seen = set()): if s == e: return 0 if d < 0: return inf if s in seen: return inf seen.add(i) ans = inf for x in G[i]: ans = min(ans, f(x, e, d - 1, seen) + 1) return ans |

def dls(s, e, d, seen = set()): if s == e: return 0 if d < 0: return inf if s in seen: return inf seen.add(i) ans = inf for x in G[i]: ans = min(ans, f(x, e, d - 1, seen) + 1) return ans

### Iterative Deepening Search Algorithm on Unweighted Graph

The Iterative Deepening Search (IDS) Algorithm is the combination of DFS/DLS and BFS. The idea is to incrementally perform the Depth Limit Search (DLS) until we find the solution (which will be optimal since the depth is incremented from 0), or there is none solution. We can set the max depth equal to the number of the vertices in the Graph.

The time complexity for a IDS can be computed as:

Which is

The depth d is explored once, and the nodes at depth d-1 are explored twice etc.

The IDS has the same time complexity as DFS where b is the branching factor (the number of nodes for each node) and the d is the depth. And IDS has also the same space complexity as DFS where d is the depth. Compared to DFS, the IDS is optimal/complete, it finds the shortest paths. The IDS has a better memory complexity than the Breadth First Search (BFS) Algorithm.

The code for Iterative Deepening Search:

1 2 3 4 5 6 7 8 |
def ids(G, s, e): N = len(G) # the number of vertices in the graph aka the longest path for i in range(N + 1): seen = set() ans = dls(G, s, e, d, seen) if ans != inf: return ans return inf # not found |

def ids(G, s, e): N = len(G) # the number of vertices in the graph aka the longest path for i in range(N + 1): seen = set() ans = dls(G, s, e, d, seen) if ans != inf: return ans return inf # not found

The Iterative Deepening Search Algorithm to sum the shortest paths/costs between pairs of vertices is given as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution: def solve(self, G, paths): @cache def ids(i, j): N = len(G) + 1 def dls(i, j, seen, depth): if i == j: return 0 if i in seen: return inf if depth < 0: return inf seen.add(i) ans = inf for x in G[i]: ans = min(ans, dls(x, j, seen, depth - 1) + 1) seen.remove(i) return ans for d in range(N): x = dls(i, j, set(), d) if x < inf: return x return 0 return sum(ids(i, j) for i, j in paths) |

class Solution: def solve(self, G, paths): @cache def ids(i, j): N = len(G) + 1 def dls(i, j, seen, depth): if i == j: return 0 if i in seen: return inf if depth < 0: return inf seen.add(i) ans = inf for x in G[i]: ans = min(ans, dls(x, j, seen, depth - 1) + 1) seen.remove(i) return ans for d in range(N): x = dls(i, j, set(), d) if x < inf: return x return 0 return sum(ids(i, j) for i, j in paths)

#### Shortest Path Algorithms

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

1550 words

**Last Post**: Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms **Next Post**: Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph)

Source: Internet