Bellman Ford Algorithm relaxation

Question

In the Bellman-Ford algorithm's relaxation part, I can't seem to understand why we need to use (d[v] = min{ d[v], d[u] + c(u, v) }), the (c(u,v)) part. This uses the original weight. Why can't it use the least cost(shortest) between (u,v) instead of c(u,v)?

Answer 1

In the relaxation step we're trying to figure out if the shortest path to the source node from v needs to go through the edge (u, v).

If the current shortest path we know - d(v) is longer than the shortest path from u d(u) plust the cost of the adge c(u,v) then we need to update d(v)'s value. Otherwise we keep d(v) as it was before.

We can't just do the minimum between d[v] and d[u] because for v to reach the source through u it needs to go through the edge (u,v) which's cost needs to be incorporated into its final distance d[v]. So if you just update d[v] to be d[u] you're ignoring the cost of the edge between them.