And initially, our x is going to be just the source for text itself.

So, now we enter the main while loop and so, remember in the while loop,

we say well, let's scan all of the edges whose tail is in the vertices we've

already looked at, whose tail is in x and whose head is outside of x.

Now, in this first iteration, there are two such edges,

there's the edge (s,v) and the edge (s,w).

So how do we know which of these two to choose?

Well, we evaluate Dijkstra's Greedy criterion.

And so remember what that is, Dijkstra's Greedy score for

a given edge (v,w) that's crossing the frontier is just the previously computed

shortest path distance for the tail of the arc plus the length of the arc itself.

So at this point, (s,v) has a greedy score of 0 + 1,

which is 1, and the arc (s,w) has a greedy score of 0 + 4, which is 4.

So obviously (s,v) is going to be the shorter of those two.

So we use the edge (s,v), this is playing the role of v*w* on the previous slide.

And the algorithm then suggests that we should add v to our set x.

So we suck in v, and our new x consists of s,

n, v, and it also tells us how to compute the shortest path distance and

the shortest path from s to v.

Namely, in the A array, we just write down what

was the Dijkstra's greedy score for this particular edge, and that was 0 + 1, or 1.

It also tells how to compute the shortest path for v.

Namely, we just inherit the shortest path to the tail of the arc,

which in this case, is the empty path from s to itself and then we tack on the end,

we append the arc we used to get here, the arc S(v).

So now we go to the next iteration of the while loop,

so with our new set capital X consisting of s and v.

And now again, we want to look at all edges which are crossing the frontier,

edges that have tail in x and head outside x.

And now we see there's three such crossing edges.

There's (s,w), there's (v,w), and there's (v,t).

All of those have the tail in x and the head outside of x.

So we need to compute Dijksta's greedy score for each of those three and

then pick the minimum.

So let's go from bottom to top.

So first of all, we can look at the arc (s,w).

And the greedy score here is the shortest path distance for the tail, so

it's 0 plus the length of the arc, which is 4.

So here we get a 4 in this iteration.

Then if we do this cross-bar edge, this (v,w) edge, the Dijkstra's greedy

score is the A value, or the shortest path distance value of the tail.

And we computed that last iteration, that A(V) value is 1,

we add to that the length of the arc, which in this case is 2.

So this edge (v,w) has a score of 3.