I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others
However, I haven't been able to find a proof of why it finds the optimal path. (In fact, most sites kind of do a bad job generalizing the algorithm itself.)
What is the proof that this algorithm always finds the optimal path in the case of a graph with 1 or more goal nodes?
Branch and Bound is similar to an exhaustive search, except it incorporates a method for computing lower bounds on branches. If the lower bound on a given branch is greater than the upper bound on the problem (i.e. the current best solution encountered), that branch can be discarded since it will never produce an optimal solution.
Hence, since you explore all options except those you know will produce values less optimal than your current best value, you are guaranteed to encounter the global optimum.
Note this is a generic algorithm, and you will need to reference a specific implementation if you want proof of why it satisfies these criteria.
My attempt was proof by contradiction. We can assume B&B found a sub-optimal path, but that would create a contradiction, because the only way B&B would miss an optimal path is if it skipped it completely (this part I don't know how to prove) or the related part of the search space was pruned.
