40.4k views
1 vote
Proof by contradiction.

Suppose we know the shortest path from A to D is A to B to C to D. Using the technique of proof by contradiction, show why the shortest path from A to C must be A to B to C.

User Swedgin
by
7.8k points

1 Answer

4 votes

Answer:

See proof below

Explanation:

For the sake of finding a contradiction, suppose that the shortest path from A to C is not A-B-C. Then, the shortest path from A to C does not cross the point B, that is, there exist some point P≠B such that A-P-C is the shortest path from A to C.

Now, consider the path A-P-C-D from A to D. This path is shortest than the path A-B-C-D, because A-P-C is shorter than A-B-C and the remaining part of both paths, C-D, contributes the same length.

More specifically, call X the length of the path A-B-C, Y to the length of the path A-P-C and Z to the lenegth of the path C-D. Then Y<X, hence Y+Z<X+Z, but Y+Z is the length of the path A-P-C-D and X+Z is the length of the path A-B-C-D.

We have found a path (A-P-B-D) from A to D shortest than the shorter path from A to D, which is a contradiction. Therefore, our assumption that the shortest path from A to C is not A-B-C must be false, which implies that the shortest path from A to C must be A to B to C.

User Rwacarter
by
8.1k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories