Understanding Dijkstra's Algo

Question

I am using this reference material: http://www.cs.arizona.edu/classes/cs545/fall09/ShortestPath.prn.pdf

In page 3's last slide, it says we are relaxing the edges leaving from B. But at that point, there is no edge between B and E, eventhough B is considered in that slide! How is that possible? Is that a mistake of the author or did I missed something else?

EDIT

This is the algorithm (from that pdf):

And this is the example graph that I am talking about:

The aim is to get the shortest path between A and D. At first, the starting vertex "A" is initialized with 0 weight. Then the rest of them are assigned with infinity. That you can see it from the algo's first 3 lines. Then, next a set "S" is created which is empty. We have the Q set which is a queue, which will hold all the vertices of the graph. We, first get the minimum weighted vertex from Q. During the first time, we will get the starting vertex itself here, because we have assigned 0 in the initialization and the rest of the vertices are having infinity. So, the smaller value is 0 and there by we gets the vertex A. We add this to the set "S". Then we will loop through all the adjacent vertices of this vertex "A" and we will check whether the weight of the vertex is greater than that of vertex "A". If so, the adjacent vertices weights are recalculated by adding the weight of the vertex "A" and the weight of the edge between the "A" and this adjacent vertex. This is continued till the set Q becomes empty.

That's the working which I understood.

The doubt is at this part:

How did we get the vertex "B", when we relax the edges leaving from the vertex "E" ? There is no edge between B and E!!!

I hope you got the idea regarding my issue now. I think you would be getting little more idea if you look at the pdf rather than my stupid explanation. Isn't it? :P That's why I put the link too in the beginning of this question!

Answer 1

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), add p[v] = u. This way, you have preserved information on how you got the current d[v], i.e. by taking the shortest path to u and then take edge u->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 that p[C]=A. Therefore, the path is ACB.