What is the key concept used in Bellman-Ford Algorithm to ensure the optimality of the solution?

The key concept used in the Bellman-Ford Algorithm to ensure the optimality of the solution is "Relaxation".

Here are the steps to explain this concept:

1. Initialization: At the beginning, the distance to the source vertex is set to 0, and for all other vertices, this distance is set to infinity. This is because we are only certain about the distance of the source vertex (which is 0 as a vertex to itself has no distance). The distance to all other vertices is set to infinity as we are not sure about the shortest distance to reach them.

2. Relaxation: The next step is to iteratively relax the edges. Relaxing an edge means finding the shortest path to the end vertex of that edge using the start vertex. This is done by summing the distance to the start vertex and the weight of the edge. If this sum is less than the current distance to the end vertex, then this distance is updated with the sum. This process is done for all edges and repeated |V| - 1 times, where |V| is the number of vertices.

3. Check for Negative-Weight Cycles: The Bellman-Ford algorithm also checks for negative-weight cycles. If we can still relax the edges after |V| - 1 iterations, then there is a negative-weight cycle, and we cannot find the shortest path. This is because the presence of a negative-weight cycle means we can loop around the cycle an infinite number of times to keep reducing the distance.

The relaxation process ensures the optimality of the solution as it guarantees that we find the shortest path to each vertex.