Difference between revisions of "TADM2E 6.15"
(name change) |
|||
| 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. | 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. | ||
| + | |||
| + | |||
| + | 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: | ||
| + | |||
| + | Following graph: | ||
| + | |||
| + | A-1-B | ||
| + | A-3-C | ||
| + | B-2-C | ||
| + | B-4-D | ||
| + | C-3-D | ||
| + | |||
| + | Minimum spanning tree would be A-B-C-D | ||
| + | Shortest-path spanning tree rooted at vertex B would be B->A, B->C, B->D | ||
| + | |||
| + | Minimum spanning tree will not change if we add arbitrary d to every edge weight. | ||
| + | Shortest-path spanning tree will change - e.g. adding -1 will change it to B->A, B->C->D | ||
Revision as of 19:00, 21 December 2015
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.
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:
Following graph:
A-1-B A-3-C B-2-C B-4-D C-3-D
Minimum spanning tree would be A-B-C-D Shortest-path spanning tree rooted at vertex B would be B->A, B->C, B->D
Minimum spanning tree will not change if we add arbitrary d to every edge weight. Shortest-path spanning tree will change - e.g. adding -1 will change it to B->A, B->C->D
