Paths in graphs 2

Question 1

Can we be sure that the distance from S to C is 5?

https://drive.google.com/file/d/1qjb2mkleNRcZIZoLYmMjqkbQPCd1Tb0p/view?usp=sharing

Yes
No

Question 2

If both dist[v]=infty and dist[u]=infty and w(u,v)=5, should the edge (u,v) be relaxed?
No
Yes

Question 3

What is the next vertex for which we already know the correct distance?

https://drive.google.com/file/d/1Um5panlSTTmtda7mZbsgNbMlTpcUF40D/view?usp=sharing

B
C
D

Question 4

What should the ExtractMin procedure do?

https://drive.google.com/file/d/1nrLo2TFQnyiaLugtK8rKLciyBoWMFSKQ/view?usp=sharing

Return the vertex in H with the minimum dist-value

Find the vertex in H wih the minimum dist-value, remove it from H and return this vertex

Remove the vertex with the minimum dist-value from H

Question 5

What is the distance d(S,S) from S to itself?

d(S,S)=0
d(S,S)=-infty
d(S,S)=4

Question 6

Why do we call cycle EUR –> GBP –> NOK –> EUR negative?

Because 0.8+12.5+0.11<0
Because 0.812.50.11=1.1>1, so
(-log2(0.8))+(-
log2(12.5))+(-
log2(0.11))=-log2(1.1)<0