Optimal Paths (Leaving Cert Applied Maths): Flashcards
📚Flashcards
Practise the cards
12 cards from this deck
ShowHide
Practise the cards
12 cards from this deck
What is Dijkstra's Algorithm?
What is Dijkstra's Algorithm?
A method to find the shortest path between nodes in a weighted graph
3 meanings of 'shortest' in context
3 meanings of 'shortest' in context
Distance, time, or cost
Weights in graph
Weights in graph
Numbers on edges connecting nodes
Dijkstra's real-world applications
Dijkstra's real-world applications
GPS, network routing, transport planning, emergency services
Starting node's initial value
Starting node's initial value
Rule for selecting next node
Rule for selecting next node
Choose smallest working value
Table components in Dijkstra's
Table components in Dijkstra's
Node, order, final value, working values
How to trace shortest path
How to trace shortest path
Work backwards using 'came from' data
When to update working values
When to update working values
After completing a node, for connected nodes
Meaning of final value
Meaning of final value
Shortest distance from start node
Algorithm completion condition
Algorithm completion condition
All nodes completed
Multiple paths to same node rule
Multiple paths to same node rule
Keep smallest working value