TADM2E 6.15 - Revision history

GreatSalmon at 21:45, 11 April 2016

2016-04-11T21:45:29Z

Zholnin at 19:00, 21 December 2015

2015-12-21T19:00:46Z

Dentin: name change

2015-04-23T19:06:19Z

name change

Algowikiadmin: Recovering wiki

2014-09-11T18:13:50Z

Recovering wiki

New page

Yes. By observation. When using Dijkstra'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.

@@ 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.
-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-4-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
-Minimum spanning tree will not change if we add arbitrary d to every edge weight.
+B-D

← Older revision		Revision as of 19:00, 21 December 2015
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

← Older revision		Revision as of 19:06, 23 April 2015
Line 1:		Line 1:
−	Yes. By observation. When using ~~Dijkstra~~'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.