hardDSA

When would you use BFS over Dijkstra for shortest paths?

Q: When would you use BFS over Dijkstra for shortest paths?

**Intuition.** Both find shortest paths, but they're optimised for different graphs. **BFS** assumes every edge costs the same (it counts *hops*), so it's pure O(V+E). **Dijkstra** handles *weighted* edges with a priority queue, paying an extra log factor. On an unweighted graph, BFS gives the same answer faster and simpler. Unweighted → BFS <line x1="120" y1="40" x2

646 views

Understand the problem

Compare BFS and Dijkstra.

graphsshortest-path

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

BFS shortest path (unweighted)

Run Playground

from collections import deque

def bfs_shortest(graph, src, dst):
    q = deque([(src, 0)])
    seen = {src}
    while q:
        node, dist = q.popleft()
        if node == dst:
            return dist
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)
                q.append((nb, dist + 1))
    return -1


# --- demo ---  unweighted graph
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print(bfs_shortest(graph, 0, 4))   # 3

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

What is the difference between Kruskal's and Prim's MST algorithms?

How do you compute the edit distance between two strings?