Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsShortest path algorithms

Bellman–Ford algorithm

Modified complexity

Report a typo

We want to modify our Bellman-Ford algorithm to return not only the array of distances but also the paths themselves. As we mentioned, this can be achieved using backtracking: if relaxation along the edge $(u,v)$ is successful, store the index $u$ in an array $p_v$ . Denote $|V| = n, \; |E|=m$ .

What will be the time complexity of our algorithm after the modification?

Select one option from the list

___

Create a free account to access the full topic