TADM2E 6.15

No. Any graph with a min path tree not satisfying the triangular inequality will not have this property. There is a constant k that you can add to all edges so that the triangular inequality will hold.

Example:

A-1-B

A-3-C

B-1-C

B-4-D

C-1-D

Note that the triangular inequality does not hold between B and D, as you can pass through C. The min path tree from B here is: B-A

B-C

C-D

Now add k=10. Now the triangular inequality does hold between B and D. The min path tree from B is:

B-A

B-C

B-D