Djikstras algorithm

Question 1

what is djikstras algorithm

Answer 1

finding the shortest path

Question 2

what are the rules for the algorithm

Answer 2

1. every time we set out to visit a new node, we will choose the node with the smallest known distance to visit first
2. once weve moved to the node were going to visit, we will check each of its neigbouring nodes
3. for each neigbouring node, calculate the distance
4. if the distance to a node is less than a known distance, update the shortest distance that we have on file for thast vertex

Question 3

explain the circumstances in which it would be more appriate to use an adjacency list instead of an adjamcency matrix

Answer 3

• graph is sparse
• when edges rearely change