Difference between revisions of "TADM2E 6.15"

From Algorithm Wiki
Jump to: navigation, search
 
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:
  
−
I believe the above is incorrect. Question asks about "shortest-path spanning tree rooted at a vertex v". Above is correct for minimum spanning tree. Simple example:
+
A-1-B
  
−
Following graph:
+
A-3-C
 +
 
 +
B-1-C
  
−
A-1-B
 
−
A-3-C
 
−
B-2-C
 
 
B-4-D
 
B-4-D
−
C-3-D
 
  
−
Minimum spanning tree would be A-B-C-D
+
C-1-D
−
Shortest-path spanning tree rooted at vertex B would be B->A, B->C, B->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
  
−
Minimum spanning tree will not change if we add arbitrary d to every edge weight.
+
B-D
−
Shortest-path spanning tree will change - e.g. adding -1 will change it to B->A, B->C->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"