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

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

• 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) —