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
- Graph Representation - Adjacency Matrix
- Graph Representation - Adjacency List
- Directed Graph
- Undirected Graph
- Weighted Graph
- BFS
- DFS
- Connected Components
- Cycle Detection
- Bipartite Graph
- Topological Sort
- Kahn's Algorithm
- DFS Topological Sort
- Shortest Path - Dijkstra
- Shortest Path - Bellman-Ford
- Shortest Path - Floyd-Warshall
- Minimum Spanning Tree - Prim's
- Minimum Spanning Tree - Kruskal's
- Disjoint Set Union - DSU
- Union-Find
- Strongly Connected Components - Kosaraju
- Strongly Connected Components - Tarjan
- Bridges
- Articulation Points
- Euler Path / Circuit
- Hamiltonian Path / Cycle
- Graph Coloring
- Network Flow
- Maximum Flow
- Bipartite Matching