14 An introduction to graphs: Finding paths of minimum distance
This chapter covers
- Introducing graphs from a theoretical point of view
- Learning strategies for implementing graphs
- Finding the best route for deliveries
- Introducing search algorithms on graphs: BFS and DFS
- Using BFS to find the route that traverses the fewest blocks
- Finding the shortest route with Dijkstra’s minimum distance algorithm
- Finding the quickest route with A* algorithm for optimal search
We already described the basics of trees in appendix C and used several kinds of trees in the previous chapters: binary search trees, heaps, k-d trees, and so on. You should now be familiar with them. Graphs could be considered a generalization of trees, although in reality the opposite ...
Get Advanced Algorithms and Data Structures now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
