Shortest Paths and Breadth First Search
Benny Chor, Amir Rubinstein · Cambridge University Press eBooks · 2022
In this chapter, we introduce the notion of graph algorithms , which are basically algorithms working on graphs. There are many such algorithms, aimed at solving a wide range of problems. We will focus on one such problem – the shortest paths problem . This problem has several algorithms, under different constraints, that solve it. We will present the well-known breadth first search (BFS), algorithm that solves a simple version of that problem. This algorithm will be explained in detail and implemented in Python. We will conclude the chapter by mentioning additional common problems in graph theory.