TADM2E 6.7 - Revision history

Matt: Undo revision 1089 by FuckMatt (talk)

2020-08-01T00:48:14Z

Undo revision 1089 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:14:17Z

Redirected page to UNTV

Jifalops: /* Part B */

2018-11-30T16:44:56Z

‎Part B

Jifalops: /* Part B */

2018-11-30T16:44:09Z

‎Part B

Zholnin at 20:40, 18 December 2015

2015-12-18T20:40:18Z

Dentin: create page

2015-04-23T18:20:13Z

create page

New page

=== Part A ===

Probably yes. Using Kruskal's algorithm, you'll still get the same insertion order of edges, regardless of how much you add or subtract from the edge weighting.

=== Part B ===

Yes, as long as negative weight edges are not allowed.

← Older revision		Revision as of 00:48, 1 August 2020
Line 1:		Line 1:
−	~~#REDIRECT [[UNTV]]~~	+	=== Part A ===
		+
		+	Probably yes. Using Kruskal's algorithm, you'll still get the same insertion order of edges, regardless of how much you add or subtract from the edge weighting.
		+
		+
		+	=== Part B ===
		+
		+	No. Example would be the following graph:
		+
		+	<pre>
		+	A -1 B
		+	B -1 C
		+	A -1 C
		+	</pre>
		+
		+	Shortest path from A to C is A->B->C.
		+
		+	If we increase all weights by two, shortest path will change to A->C

← Older revision		Revision as of 10:14, 31 July 2020
Line 1:		Line 1:
−	~~=== Part A ===~~	+	#REDIRECT [[UNTV]]
−
−	~~Probably yes. Using Kruskal's algorithm, you'll still get the same insertion order of edges, regardless of how much you add or subtract from the edge weighting.~~
−
−
−	~~=== Part B ===~~
−
−	~~No. Example would be the following graph:~~
−
−	~~<pre>~~
−	~~A -1 B~~
−	~~B -1 C~~
−	~~A -1 C~~
−	~~</pre>~~
−
−	~~Shortest path from A to C is A->B->C.~~
−
−	~~If we increase all weights by two, shortest path will change to A->C~~

@@ Line 9: / Line 9: @@
 <pre>
-A -1-> B
+A -1 B
-B -1-> C
+B -1 C
-A -3-> C
+A -1 C
 </pre>

@@ Line 8: / Line 8: @@
 No. Example would be the following graph:
 A -1-> B
 B -1-> C
 A -3-> C
 Shortest path from A to C is A->B->C.
 If we increase all weights by two, shortest path will change to A->C

← Older revision		Revision as of 20:40, 18 December 2015
Line 6:		Line 6:
	=== Part B ===		=== Part B ===

−	~~Yes~~, ~~as long as negative weight edges are not allowed.~~	+	No. Example would be the following graph:
		+
		+	A -1-> B
		+	B -1-> C
		+	A -3-> C
		+
		+	Shortest path from A to C is A->B->C.
		+
		+	If we increase all weights by two, shortest path will change to A->C