MTH6105 Algorithmic Graph Theory
Week 4: Shortest Paths
||Covered this week:
- Lecture 1:
- Kruskal's Algorithm
Notes carried over from Week 3.
- Lecture 2:
- Dijkstra's Algorithm. Notes
- Lecture 3:
- Complexity and correctness of Dijkstra. Going further: digraphs, negative weights, longest paths. Notes
Week 4 Coursework: watch the boxes below!
More on the web!
for a (directed version of) Dijkstra's Algorithm
offering 'animations' of several of the algorithms on this module, including Dijkstra
An in-depth discussion
of Dijkstra's Algorithm: history, variations, etc etc