Decision 1 Unit 4

Question 0

How are the boxes for Dijkstra’s Algorithm presented?

Answer 0

|____|____|.
|________|.
The first box is for the order that it is labelled. The second is the permanent amount that it is labelled as. The bottom is the working values from the start which change.

Question 1

What is Dijkstra’s Algorithm used for?

Answer 1

To find the shortest route from one node to another.

Question 2

How to use Dijkstra’s Algorithm?

Answer 2

1. Label the staring node (S) 1 and a permanent value of 0.
2. Give each node connected to S a working value which is its distance from S.
3. Find the smallest working value and use this as a permanent value for that node and label it 2.
4. Repeat by finding any new or smaller working values and selecting the smallest etc until a route is found.

Question 3

How to find the shortest route from the permanent labels?

Answer 3

Starting at the end node, take away the permanent label of a connecting node from the end node’s. If the amount is the same as the arc then it could have came this way. Repeat until back to start.
Remember to check for more than one route.

Question 4

What is the order of Dijkstra’s algorithm?

Answer 4

n^2