# Further Maths - Dijkstra's Algorithm

> Source: https://ollybritton.com/notes/a-level/further-maths/topics/dijkstras/ · Updated: 2024-08-24 · Tags: school, year-2, decision, further-maths

## Flashcards
##### What are the three values you should store for each vertex in Dijkstra's??
![PHOTO DIJKSTRAS BOX](paste-0d4e31d34235f413435c8495dd5543de654a4646.jpg)

##### Once you've labelled the end vertex with a permanent label in Dijkstra's, what can you do??
Stop and save yourself the work of labelling every vertex.

##### What does Dijkstra's algorithm do??
Tell you the shortest distance from any node to the start node.

##### At each step of Dijkstra's algorithm, what should you do??
* Look at the verticies connected to the most recently permanently labelled node.
* Update the minimum cost if it is lower.
* Label the next vertex with the smallest cost.

##### ![PHOTO DIJKSTRAS NEXT STEP](paste-fe3ad09035739f529ca3e7bc7f00fdae54d1f5a2.jpg) C has just been given a permanent label. What is the next step??
Updating the working values for every connection if it is lower.

##### How should you generate the list of nodes for the shortest path for a start vertex and an end vertex??
Start at the end vertex and successively choose the nodes whose permanent value and path cost sum to the best value labelled.

##### ![PHOTO DIJKSTRAS BACKTRACKING](paste-3dacd1f71a75d0e237dfe9a1312a37c0abb8af38.jpg) Which node out of $D$ and $F$ is the previous vertex in the shortest path sequence from $A$ to $G$??
$$
D
$$

##### Why should you continue to check the label sums when backtracking for Dijkstra's even after you've found one that works??
There might be another one that gives an alternate route.

### 2021-11-17
##### What is the worst case time complexity of Dijkstra's??
$$
O(n^2)
$$

##### How can you work out the shortest route using Dijkstra's if you need to stop at a node in the middle??
Treat it as two separate problems.

### 2022-06-08
##### How could you add a delay of 6 minutes for every route passing through a certain node in a network??
Add 3 minutes to the weight of every arc it's connected to.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt