Book contents
- Computational Thinking for Life Scientists
- Reviews
- Computational Thinking for Life Scientists
- Copyright page
- Dedication
- Contents
- Introduction
- Part I: Programming in Python
- Part II: Sequences
- Part III: Graphs and Networks
- 5 Basic Notions in Graph Theory
- 6 Shortest Paths and Breadth First Search
- 7 Simulation of Regulatory Networks
- Part IV: Images
- Part V: Limitations of Computing
- Index
- References
6 - Shortest Paths and Breadth First Search
from Part III: - Graphs and Networks
Published online by Cambridge University Press: 19 August 2022
- Computational Thinking for Life Scientists
- Reviews
- Computational Thinking for Life Scientists
- Copyright page
- Dedication
- Contents
- Introduction
- Part I: Programming in Python
- Part II: Sequences
- Part III: Graphs and Networks
- 5 Basic Notions in Graph Theory
- 6 Shortest Paths and Breadth First Search
- 7 Simulation of Regulatory Networks
- Part IV: Images
- Part V: Limitations of Computing
- Index
- References
Summary
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.
- Type
- Chapter
- Information
- Computational Thinking for Life Scientists , pp. 113 - 122Publisher: Cambridge University PressPrint publication year: 2022