Skip to main content

Shortest Path - BFS

Learn Shortest Path - BFS (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Shortest Path in an Unweighted Graph with BFS When every edge has the same cost (or no weight), the shortest path is the one with the fewest edges . Breadth-first search finds it: it visits vertices in rings, all vertices 1 edge away, then 2 edges away, and so on, so the first time a vertex is reached is by a shortest route. Record a distance and a parent for each vertex; follow the parents back to rebuild the path. Cost: O(V + E) .

More lessons in Graphs