Network Algorithms Flashcards
Explain how Dijkstras algorithm works
The weights on the arcs can represent different things that might lead to alternate routes. For example, they could represent the time taken to travel a stretch of road rather than distance.
The temporary and permanent values are for the quickest and slowest routes to that particular node.
The algorithm systematically searches for the quickest route to every node. We assign a temporary label as that stands for the current quickest route to that node. Later in the algorithm an alternative route may be found so we replace the temporary label with a new temporary label.
All routes up to a certain point have been covered, so the node with the lowest temporary label must be the next nearest node to the starting point.
