Dijkstra’s Shortest Path Algorithm (AQA A-Level Computer Science): 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 most efficient route between points in a network
Who created Dijkstra's algorithm and when
Who created Dijkstra's algorithm and when
Edsger Dijkstra in 1959
Data structure used by Dijkstra's algorithm
Data structure used by Dijkstra's algorithm
Graph (with vertices/nodes and edges)
Type of graph Dijkstra's algorithm requires
Type of graph Dijkstra's algorithm requires
Weighted graph with positive weights only
Critical limitation of Dijkstra's algorithm
Critical limitation of Dijkstra's algorithm
Only works with positive edge weights
Single source concept in Dijkstra's algorithm
Single source concept in Dijkstra's algorithm
Calculates shortest path from one start vertex to all others
How to select next vertex in Dijkstra's algorithm
How to select next vertex in Dijkstra's algorithm
Always move to nearest unvisited vertex
Rule when multiple routes exist to same vertex
Rule when multiple routes exist to same vertex
Always keep the shortest distance
Best structure to represent weighted graph in code
Best structure to represent weighted graph in code
Two-dimensional array (adjacency matrix)
Purpose of subscripts when tracing Dijkstra's algorithm
Purpose of subscripts when tracing Dijkstra's algorithm
Show which vertex you travelled from to reach current distance