Shortest Path Algorithms (Edexcel A-Level Further Mathematics): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Purpose of Dijkstra's algorithm
Purpose of Dijkstra's algorithm
Finds shortest path from starting node to all others
Starting node's initial distance
Starting node's initial distance
Other nodes' initial distance
Other nodes' initial distance
(infinity)
Tentative distance calculation formula
Tentative distance calculation formula
Current node distance + edge weight
When to update neighbour's distance
When to update neighbour's distance
When calculated distance current recorded distance
Next node selection rule
Next node selection rule
Unvisited node with smallest tentative distance
Dijkstra's termination condition
Dijkstra's termination condition
Shortest path to target found or all nodes visited
Visited nodes in further steps
Visited nodes in further steps
Not checked again
Initialisation mistake
Initialisation mistake
Forgetting start=, others=
Edge weight mistake
Edge weight mistake
Treating all edges as equal weight