Dijkstra’s Algorithm

Videos

Introduction 1

https://www.youtube.com/watch?v=pVfj6mxhdMw

Introduction 2

https://www.youtube.com/watch?v=GazC3A4OQTE

Challenge

Programming Challenge

Using Python program an implementation of Dijkstra’s algorithm to find the shortest driving distance between two cities using the data provided.

UK Road Graph

UK Road Sheets File (Download as CSV to use within your program)

UK Roads Matrix

Limitations

Limitations of Dijkstra’s Algorithm

A lack of heuristics

 

directed networks

 

Internet Routing

Internal Routing with Shortest Path

https://www.youtube.com/watch?v=AkxqkoxErRk

 

 

Resources

Resources

 

Teacher Presentation

Example Work-through Google Sheet

Worksheets

https://www.tes.com/teaching-resource/dijkstra-s-algorithm-6147438

 

https://courses.cs.washington.edu/courses/cse373/13au/lecture15.pdf

 

https://courses.cs.washington.edu/courses/cse373/13au/midterm2Unsolved.pdf   (page  9 negative costs question)

 

https://www.pearsonschoolsandfecolleges.co.uk/secondary/Mathematics/16plus/AdvancingMathsForAQA2ndEdition/Samples/SampleMaterial/Chp-02%20023-043.pdf