Further Maths - Dijkstra's Algorithm
Flashcards
What are the three values you should store for each vertex in Dijkstra’s?
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.
C has just been given a permanent label. What is the next step?
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.
Which node out of $D$ and $F$ is the previous vertex in the shortest path sequence from $A$ to $G$?
Which node out of $D$ and $F$ is the previous vertex in the shortest path sequence from $A$ to $G$?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?
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.