Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

Breadth First Search Algorithm (BFS) performs a level by level order, and we can use this algorithm to get the shortest path in a unweighted graph. The BFS Algorithm uses a Queue which is a First In First Out Data Structure.

The BFS code works like this:

1
2
3
4
5
6
7
8
9
10
11
12
13

def BFS(G, s, e):
    if s == e:
        return 0
    q = deque([(0, s)])
    seen = set()
    while q:
        c, v = q.popleft()
        if v in seen:
            return c
        seen.add(v)
        for x in G[v]:
            q.append((c + 1, x))
    return inf

def BFS(G, s, e):
    if s == e:
        return 0
    q = deque([(0, s)])
    seen = set()
    while q:
        c, v = q.popleft()
        if v in seen:
            return c
        seen.add(v)
        for x in G[v]:
            q.append((c + 1, x))
    return inf

We use a hash set to remember the vertices that have been visited. For Breadth First Search Algorithm, this check can be done also when the elements are about to be enqueud like this:

1
2
3
4
5
6
7
8
9
10
11
12

def BFS(G, s, e):
    if s == e:
        return 0
    q = deque([(0, s)])
    seen = set()
    while q:
        c, v = q.popleft()
        for x in G[v]:
            if x not in seen:    
                seen.append(x)
                q.append((c + 1, x))
    return inf

def BFS(G, s, e):
    if s == e:
        return 0
    q = deque([(0, s)])
    seen = set()
    while q:
        c, v = q.popleft()
        for x in G[v]:
            if x not in seen:    
                seen.append(x)
                q.append((c + 1, x))
    return inf

The time complexity is because in the worst case, all edges and vertices in the (unweighted) graph (or graph with equal weights) are explorered.

The Uniform Cost Search (UCS) Algorithm is a variant of Dijkstra.

We can just change the queue (FIFO) to priority queue (or heap) on the basis of the first BFS and that is basically UCS:

1
2
3
4
5
6
7
8
9
10
11
12
13

def UCS(G, s, e):
    if s == e:
        return 0
    q = [(0, s)]
    seen = set()
    while q:
        c, v = heappop(q)
        if v in seen:
            return c
        seen.add(v)
        for x, w in G[v]:
            heappush(q, (c + w, x))
    return inf

def UCS(G, s, e):
    if s == e:
        return 0
    q = [(0, s)]
    seen = set()
    while q:
        c, v = heappop(q)
        if v in seen:
            return c
        seen.add(v)
        for x, w in G[v]:
            heappush(q, (c + w, x))
    return inf

Unlike BFS, UCS can be used on weighted graph. The above G is a adjacent list graph representation.

The Dijkstra algorithm adds step of “Updating the Estimates” and thus keeps a one-dimensional array e.g. d that stores the shortest distance from the source. The Dijkstra algorithm is complete as it computes all shortest path from the source while the BFS and UCS are not complete aka they only return the shortest path between a pair of vertice.

Both Dijkstra and UCS runs at time complexity

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