And same way with edgeTo[v] of course.

Now, so to relax along the edge from v to w, essentially that means,

let's update the data structures to take that edge into account.

And what happens in this case is that the edge gives a better way to get to w.

So that's what relaxing is.

That edge gives us a new shortest path.

So we want to include it in the data structures.

So since it has a shorter path, we have to update both distTo[w] and edgeTo[w].

That is we have a new way to get to w, because we have to throw away that old

edge that came to w and we have a new shorter distance.

Instead of 7.2 that came out old way, we have 4.4 that gets us a new way.

So edge relaxation is a very natural operation.

When we consider a new edge, does it give a new shortest path to that vertex or not?

If it doesn't, we ignore it.

If it does, we update the data structures to include that edge and

forget about the old edge that took us to that vertex.

That's edge relaxation.

And this is the easy implementation of edge relaxation in code.

So to relax an edge, we pull out its from and two vertices in v and

w according to our standard idiom.

And then we just see if the distance to w that was the shortest

path before is bigger than the distance to v plus

the weight of the edge that would take us from v to w.

[COUGH] If it's bigger, that means we found a new path.

If it's less than or equal, we ignore it.

And if we found a new path, we have to update the distance to w to be the new

distance, distance to v plus follow vw.

And then we have to update edgeTo[w] and throw away the old version.

And say that our new edge from v to w is the best path to w as far as we know.

So that's easy code for edge relaxation.