# Difference between revisions of "TADM2E 6.15"

From Algorithm Wiki

(Recovering wiki) |
GreatSalmon (Talk | contribs) |
||

(2 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

− | + | 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 |

## Latest revision as of 21:45, 11 April 2016

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