SME
Computer Networks · Problem type
Dijkstra’s order
Use this for “In what order does Dijkstra’s algorithm finalise the routers from S?”
Put in order
Put the routers in the order Dijkstra’s algorithm finalises them.
1
?
2
?
3
?
4
?
5
?
Assumptions
•
Link costs are positive, so a finalised distance can never get smaller later.
•
Each step finalises the unvisited router with the smallest distance so far.
•
A router’s distance is the one it was reached at, through the lit link.
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.