Algorithms - lesson 6 | HackIndia Skills

Algorithms - lesson 6 | HackIndia Skills | HackIndia

Example

BFS shortest path

This is the pattern for minimum buses, minimum roads, or minimum friend links when every edge has equal cost.

Save this as graphs/bfs_shortest_path.py in your repo.

from collections import deque

def shortest_path(n, edges, start, target):
    graph = [[] for _ in range(n)]

    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)  # remove this line for a directed graph

    dist = [-1] * n
    dist[start] = 0
    q = deque([start])

    while q:
        node = q.popleft()
        if node == target:
            return dist[node]

        for nei in graph[node]:
            if dist[nei] == -1:
                dist[nei] = dist[node] + 1
                q.append(nei)

    return -1

if __name__ == "__main__":
    n = 6
    edges = [(0, 1), (0, 2), (1, 3), (2, 4), (4, 5)]
    print(shortest_path(n, edges, 0, 5))  # 3

Example

README note

For every graph solution, write what the nodes and edges mean. A recruiter should not guess your model.

Add a small complexity note beside the code file.

### Graph traversal: shortest path in unweighted graph

File: graphs/bfs_shortest_path.py

Approach:
- Build an adjacency list from the edge list.
- Run BFS from the start node.
- Store distance in edges from the start.
- Return -1 if the target is not reachable.

Complexity:
- Time: O(V + E), because each node and edge is processed at most once.
- Space: O(V + E), for the graph, queue, and distance array.

Graph traversal for placements

Why graphs matter

One idea

Build the graph

BFS shortest path

Use AI carefully

Common bug

README note

Do this now

Quick check