Shortest path with breadth-first search
Find the fewest edges between two vertices in an unweighted graph.
Course progress
Problem 34 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
start = 1; target = 5; unweighted graph edges as shown in the solution
Expected output
3
What is happening?
Breadth-first search reaches vertices by distance. A shortest route is 1 -> 2 -> 4 -> 5, which uses three edges.
Solution strategy
Build the right mental model
Breadth-first search visits vertices one distance layer at a time. Record each vertex when it is enqueued so cycles cannot add it repeatedly.
Core concepts
graph · queue · BFS
Complexity
Time O(V + E), space O(V).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for shortest-path-bfs
using System;
using System.Collections.Generic;
class Program
{
static int ShortestDistance(Dictionary<int, int[]> graph, int start, int target)
{
var queue = new Queue<int>();
var distances = new Dictionary<int, int>();
queue.Enqueue(start);
distances[start] = 0;
while (queue.Count > 0)
{
int current = queue.Dequeue();
if (current == target) return distances[current];
foreach (int neighbor in graph[current])
{
if (distances.ContainsKey(neighbor)) continue;
distances[neighbor] = distances[current] + 1;
queue.Enqueue(neighbor);
}
}
return -1;
}
static void Main()
{
var graph = new Dictionary<int, int[]>
{
{ 1, new[] { 2, 3 } }, { 2, new[] { 1, 4 } },
{ 3, new[] { 1, 4 } }, { 4, new[] { 2, 3, 5 } }, { 5, new[] { 4 } }
};
Console.WriteLine(ShortestDistance(graph, 1, 5));
}
}Knowledge check
Questions students often ask
What is the main idea behind shortest path with breadth-first search?
Breadth-first search visits vertices one distance layer at a time. Record each vertex when it is enqueued so cycles cannot add it repeatedly.
What is the time and space complexity of this solution?
Time O(V + E), space O(V).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.