d[v]
means: the length of the shortest path between the node v
and the starting point by going through nodes that are in S
only.
Despite node E does not connect to B, we have learned from previous iterations that a path of length 7 exist from A
to B
by going through A
and C
only. We can certainly deduce that the same path exists by going through A
, C
, and E
only.
Note that in the highlighted section of the code in the first slide, it updates d[v]
only if a smaller value exists. If not, d[v]
remains unchanged.
I have noticed that the OP is confused about S
. I would like to add that in this algorithm, S
is only useful in the sense that it can help explain what the program is doing. (I used it when I explained to you what d[v]
means.) S
has not effect on the program at all. The program works the same if you remove S
from the program completely.
This program does NOT provide you the shortest path. It only tells you the length of the shortest path between the starting node and every node in the graph.
If you want to get the shortest path, the program need to be revised to add this feature. Here are the steps:
- In the then clause of the program, either before or after
d[v] = d[u] + w(u,v)
, addp[v] = u
. This way, you have preserved information on how you got the currentd[v]
, i.e. by taking the shortest path tou
and then take edgeu->v
. - After the whole program finishes (i.e. after the while loop), say you want to know what the shortest path is from A to B. You will find out that
p[B]=C
, and then you will find out thatp[C]=A
. Therefore, the path isACB
.