Bellman Ford: Why do we need to use the same vertex with edgesAllowed - 1 in the bellman ford recursive recurrence

Question

So below is the usual bellman ford recurrence

But why do we need to make a call to OPT(v, i-1) given that the shortest path to the vertex v must include the neighbouring vertex u in its shortest path from s to v where (u, v) is an edge in the set of Edges of the graph. This applies to all vertices except for the source vertex, so I guess that the call OPT(v, i-1) is only made to handle the case of calling OPT(s, i) so i must keep decrementing to reach i = 0, so that we could return 0.

But couldn't we just modify the recurrence to exclude the need to make a call to OPT(v, i-1) by modifying our base case as following:

NOTE: I assume the graph has no negative weight cycles reachable from the source vertex just to make my claim easier to reason with

Answer 1

If you mean $\text {if } i > 0 \text{ and } v \ne s$ as condition for the last line, then you are right. However then you lose an opportunity to check whether there is a negative cycle containing the vertex $s$.

The sketch of correctness proof for the original algorithm is the following: $\mathrm{OPT}(v, i)$ is the minimum length of $(s, v)$-walk with at most $i$ arcs, and the recurrent formula corresponds to this definition.

For your modification the meaning of $\mathrm{OPT}(v, i)$ firstly should be changed a bit. Now it means the minimum length of $(s, v)$-walk with at most $i$ arcs and only one appearance of $s$. For a graph with no negative cycles this difference is not important. But for a graph with such cycles it is.