Book Club: Grokking Algorithms. 5: Dijkstra's algorithm, greedy algorithms
Tags: books, algorithms, bookclub
Published: 2023-08-29 16:23:52

---
title: Book Club: Grokking Algorithms. 5: Dijkstra's algorithm, greedy algorithms
published: true
description: Book Club discussion for Grokking Algorithms by Aditya Y. Bhargava
tags: [books, algorithms, bookclub]
series: ["book club Grokking Algorithms"]
---

#### **Grokking Algorithms** An _illustrated_ guide for programmers and other curious people, by Aditya Y. Bhargava

-----

## Chapter 7: Dijkstra's algorithm
## Chapter 8: Greedy algorithms

If you read any of these chapters, please go ahead and discuss what you thought in the comments! 

:memo: you can read my notes below.

:calendar: The next post will be on chapters 9 - 10. I'll aim for September 2023.
If you're on [Storygraph](https://app.thestorygraph.com/profile/ruthmoog) and want to join me, say hi and I'll start a Buddy Read.

-----

## Dijkstra's algorithm

key topics in this chapter: `weighted graphs`, `unweighted graphs`, `Dijstra's algorithm`, `cycles`, `positive and negative weighting` ...

The shortest path from A to B is not always the fastest path. Dijkstra's algo finds the fastest path, by assigning weight to the edges

### Cycles

A cycle means you can loop back to the same node.

- Following the cycle never gives you the shortest path.
- An undirected graph is a cycle
- Dijkstra's algorithm only works on
  - graphs with no cycles
  - graphs with a positive weight cycle (if the weight of a cycle is negative when looking for the shortest path, you'll be stuck in an infinite loop calculating around the ever decrementing cycle)

Path found with **Breadth-first search**:

![Breadth-first search](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/01x7ib5c07tqh3poo5uu.png)

Path found with **Dijkstra's algorithm**:

![Djikstra's algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6auuxir3kt2bqeewk9cv.png)


-----

## Greedy algorithms

Key topics covered `Impossible problems`, `NP-complete problems`, `approximation algorithms`, `greedy strategy`, `sets`, `union`, `difference`, `intersection`, `fractorial function`...

This chapter covers a few scenarios where writing accurate algorithms is difficult. I found this the hardest to get my head around, because the example algorithms are not smart my mind was automatically trying to optimise the behaviour without realising it.

Think I might need to revisit this chapter!

**The classroom scheduling problem**: Find the most classes that can be held in the classroom by selecting whichever class ends first, then repeat starting after the previous classes end.

**The knapsack problem**: If you use the process above to steal expensive items that weigh a lot for your knapsack, it won't give you the optimal solution ... but you'll get pretty close, and sometimes that's good enough.

**The set-covering problem**: Make a _power set_ (calculate everything), then choose the best answer. It takes a long time to do this... O(2<sup>^n</sup>)


![number of factorial routes](https://github.com/egonSchiele/grokking_algorithms/blob/master/images/08_greedy_algorithms/084_np_complete_problems/num_routes_factorial.png?raw=true)
<figcaption>copyright Manning Publications, drawn by adit.io</figcaption>


**The travelling salesperson**: Find the most efficient route between _x_ calling points. The number of possible routes becomes very big, very fast (fractorial function)

### NP-completeness

To figure if a problem is NP-complete, look for...

- Algorithm runs quickly with a few items but slowly with a lot of items
- "All combinations of x" usually suggests NP-completeness, combinations can't be broken into smaller solvable sub-problems
- Involves a `set` and is hard to solve
- You can restate the problem as the _set-covering problem_ or the _travelling salesperson problem_

-----

### Key Takeaways

0. Use Breadth-first search for the cheapest path in an unweighted graph, and Dijkstra's algorithm for the cheapest path in a weighted graph

0. If you have negative weights use Bellman-Ford algorithm and not Dijkstra's algorithm

0. Sets have some cool behaviours
   - Intersection (select items in BOTH sets)
   - Union (select all items)
   - Difference (select items NOT in both sets)

0. NP-complete problems are when you calculate all scenarios to figure out the shortest/smallest one
   - e.g. the travelling salesperson, set-coverage problem
   - they have no known fast solution at scale
   - it's best to use an approximation algorithm instead

0. Greedy algorithms hope to end up with a global optimum, but optimising locally
   - they're easy to write and fast to run so they make good approximation algorithms
  - Greedy algorithms: at each step, pick the optimal move

-----