enter image description here

In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path.

Can someone please explain what information I can get by looking at the above example? How can I tell what is the shortest path to where?

  • $\begingroup$ Computing any set of numbers won't help. Computer the right ones, though... $\endgroup$ – Raphael Nov 24 '14 at 19:10

In this example, the numbers on the edges are "given" - they are weights of the edges of the graph in which you want to compute the shortest paths from the source vertex S to all other vertices.

The rest of the information on this graph is the result of the shortest path computation (though this slide doesn't give the algorithm used to compute it - the algorithm is given in subsequent slides).

The result consists of two parts:

  • The numeric value of the shortest distance from S to each other node. Every node is labeled with its shortest distance. E.g. it's 0 for S itself, -2 for C, 8 for D, etc.

  • The "shortest paths tree", which allows to reconstruct the actual shortest path to any vertex, not just the length of the path. More on it below.

The actual shortest paths are encoded in a peculiar way, relying on the fact that if you take all edges that participate in at least one shortest path from S to some other vertex, you'll get a tree. Here's why:

Take any vertex - e.g. B. The shortest path from S to B is S-C-A-B. The vertex A is B's "predecessor" ("parent") in this path. For a fixed vertex S, obviously each other vertex has a predecessor (parent). On this picture, "X's predecessor is Y" is denoted as $ X.\pi = Y $.

What's a structure where each vertex has a parent? It's a tree! So we obtain a tree of shortest paths. This tree is a subset of the graph's edges. On your picture, the edges included in this subset are highlighted with red color.

This tree can be used to reconstruct the shortest path from S to any vertex. E.g., for vertex D, its parent is B, B's parent is A, A's parent is C, C's parent is S, so we get S-C-A-B-D.

Note that this tree construction relies on a certain (rather obvious) property of shortest paths: for any vertex, the shortest path to it goes through the shortest path to one of its adjacent vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.