Chapter 3 Newtork Algorithms : SHORTEST PATH (Dijkstra )

Question 1

What does DIJKSTRAS algorithm do

Answer 1

Find the shortest path from A to all points in diagram

Question 2

2 steps to doing Dijskrta?

Answer 2

Stel 1 = labelling all the vertices

Step 2 = finding the path by working backwards that finds that minimum path

Question 3

What goes in a label for a vertex

Answer 3

Top left = the order of labelling
Top right = final value

In side = working out , where the final working value goes into top right

Question 4

How to label all the vertices step 1

Answer 4

1) start at the point , label this 1 and this has a working value 0

2) look at all routed going out from A, and ADD the weights to each boxes working value

3) now look for the next box with the SMALLEST WEIGHT in the box. Once identified , you have chosen this box

4) when a box is chosen label it with next number (2), and also write down the final working value in top right!

5) now , add all the weights going out from this box to whatver itsfinal working value is. IF THIS IS BETTER (SO SMALLER) than whatver is in the next box, write comma and out it in

Now go again, look for smallest working value box, and chose it

Eventually you will have everything labelled and thus all the distances

Question 5

Part 2 of Dijkstas

How to find the route then thst takes you to the smallest path

Answer 5

WORK BACKWARDS

• start at the end post , and subtrsvt the weights from final working value .

If it gets you to the final working value of whatever successfully, pick this, if not it’s not part of route

Keep working backward and find the route

Question 6

Okay importsnt to remember, if you want to see which starting positions from 3 places will get to end point fastest, what’s modt effeicmt way of doing

Answer 6

Going from end point to three starting, because quickest from AV is same from VA

And doing this finds all 3 AT THE SAME TIME

Question 7

Complexity dijkstras?

Answer 7

O(n2)