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!
📝 you can read my notes below.
📆 The next post will be on chapters 9 - 10. I'll aim for September 2023.
If you're on Storygraph 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:
Path found with Dijkstra's algorithm:
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^n)
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
setand is hard to solve - You can restate the problem as the set-covering problem or the travelling salesperson problem
Key Takeaways
Use Breadth-first search for the cheapest path in an unweighted graph, and Dijkstra's algorithm for the cheapest path in a weighted graph
If you have negative weights use Bellman-Ford algorithm and not Dijkstra's algorithm
-
Sets have some cool behaviours
- Intersection (select items in BOTH sets)
- Union (select all items)
- Difference (select items NOT in both sets)
-
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
-
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
Top comments (2)
@ruthmoog : similar minds or coincidence my blog on Dijkstras
It IS magic! 😻
Love the excel example, thanks @balagmadhu 👍