Difference between revisions of "TADM2E 6.15"

From Algorithm Wiki
Jump to: navigation, search
(name change)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
−
Yes. By observation. When using Kruskal's algorithm you always select the edges with the minimum weight to add to the shortest path. When all weights are increased by one, you'll still select the same edge with this algorithm, therefore, the same shortest path spanning tree will still be found.
+
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

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_6.15&oldid=417"