MTH6105 Algorithmic Graph Theory

Week 4: Shortest Paths

  Covered this week:
Lecture 1:
Kruskal's Algorithm Notes PDF file iconcarried over from Week 3.
Lecture 2:
Dijkstra's Algorithm. Notes PDF file icon
Lecture 3:
Complexity and correctness of Dijkstra. Going further: digraphs, negative weights, longest paths. Notes PDF file icon

Week 4 Coursework: watch the boxes below!
Coursework 4
Solutions
Download pdf
Update: 07.02.12 to Q3
Submit: 08.02.12
Jpeg image for Q. 5
Download pdf

Extra: meet the man - visit the Dijkstra Archive!

Week 3 Week 5 Back to MTH6105 main page School of Maths Sciences