Dijkstra’s Algorithm (VCE SSCE General Mathematics): Flashcards
📚Flashcards
Practise the cards
10 cards from this deck
ShowHide
Practise the cards
10 cards from this deck
Dijkstra's algorithm purpose
Dijkstra's algorithm purpose
Find shortest path through weighted graph
Developer of Dijkstra's algorithm
Developer of Dijkstra's algorithm
Edsger Wybe Dijkstra (Dutch computer scientist)
Starting vertex value in Dijkstra's
Starting vertex value in Dijkstra's
0 (zero)
Permanence rule for circled values
Permanence rule for circled values
Cannot be changed once circled
Which uncircled value to make permanent
Which uncircled value to make permanent
The smallest uncircled value
Updating vertex from with value
Updating vertex from with value
edge weight, keep smaller if exists
When to stop the algorithm
When to stop the algorithm
When destination vertex is circled
Purpose of backtracking step
Purpose of backtracking step
Find the actual route/path
Backtracking calculation
Backtracking calculation
Vertex value - edge weight = previous vertex value
Real-world applications
Real-world applications
GPS navigation, routing, scheduling, network optimization