BFS Shortest Path
BFS Shortest Path
Given an undirected unweighted graph with n nodes (0-indexed) and m edges, find the shortest path between a given source node and a destination node. The shortest path in an unweighted graph is the one with the fewest edges. Example: 6 nodes, 7 edges, source=0, dest=5 → 3
Input format — only if your code reads from stdin
Input format: - First line: four integers n (nodes), m (edges), source, destination - Next m lines: two integers u v representing an undirected edge between u and v Output: the minimum number of edges on a path from source to destination, or -1 if no path exists.
Approach
BFS guarantees shortest paths in unweighted graphs. Use a queue initialized with source (distance 0) and a visited array. At each step, dequeue a node, process all its unvisited neighbors, enqueue them with distance+1. Return the distance when destination is reached.
Input
Output
- •
1 ≤ n ≤ 10^4, 0 ≤ m ≤ 10^5, 0 ≤ source, destination < n
More Graphs problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards