We can also compute the vertices on shortest paths as we compute the shortest-path weights. Define (m) ij as the predecessor of vertex j

We can also compute the vertices on shortest paths as we compute the shortest-path weights. Define π^(m)_ij as the predecessor of vertex j on any minimum-weight path from i to j that contains at most m edges. Modify the EXTEND-SHORTEST-PATHS and SLOW-ALL-PAIRS-SHORTEST-PATHS procedures to compute the matrices ∏⁽¹⁾,∏⁽²⁾, . . . ,∏^(n-1) as the matrices L⁽¹⁾,L⁽²⁾, . . . ,L^(n-1) are computed.