Learnearn.uk » KS3 Algorithms Unit » Pathfinding Algorithms

# Pathfinding Algorithms

## Starter

### Starter

Today we are going to be exploring different algorithms for finding the shortest path between two points.

To start have a look at the interactive game in the link provided. How do the different algorithms behave?

How does Dijkstra’s work?

Introduction 1

Introduction 2

## Limitations

### Limitations of Dijkstra’s Algorithm

Dijkstra’s algorithm is a great, simple way of finding the shortest path in most situations, however it does have 2 big weaknesses

A lack of heuristics

Dijkstra’s algorithm has no notion of the overall shortest direction to the end goal, so it will actually spend a lot of time searching in completely the wrong direction if the routes in the wrong direction are shorter than the route in the correct direction. It will find the shortest route in the end but it will waste a lot of time.

In small networks this isn’t a problem but when you have massive networks (like road networks or the internet) then it will result in massive inefficiencies.

Negative Weighted Costs

On physical networks with physical distances you can’t have negative weights, but one some networks where you are calculating costs you might have negative costs for a particular leg. Dijkstra’s cant handle these negative costs.

Directed networks

Dijkstra’s algorithm doesn’t always work best when there are directed networks (such as motorways that only run in one direction)

## Resources

### Resources

Teacher Presentation

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)

### Programming Challenge

This challenge is only for experienced Python programmers!

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