Exercise: Path-Relaxation

Test your understanding of the implications of path-relaxation of a shortest path.

We'll cover the following

The task at hand

In the digraph given below, you are required to relax only the smallest number of edges—in the correct order—so that the shortest path from the source v1v_1 to the vertex v6v_6 is calculated in the smallest number of steps.

Assume that the digraph is initialized in the prescribed way, with distdist set to 00 for v1v_1, and it's set to \infty for all other vertices.

Get hands-on with 1200+ tech skills courses.