TADM2E 6.9 - Revision history

Bkarpov96: Undo revision 878 | Why are u doing this? What's the point? It's wiki for learning book

2020-07-23T08:13:07Z

Undo revision 878 | Why are u doing this? What's the point? It's wiki for learning book

Fucs: Undo revision 874 by Bkarpov96 (talk)

2020-07-22T22:52:04Z

Undo revision 874 by Bkarpov96 (talk)

Bkarpov96: 6.9.b alternative solution

2020-07-22T14:47:47Z

6.9.b alternative solution

Dentin: Add hint

2015-04-23T18:50:32Z

Add hint

Dentin: create page

2015-04-23T18:47:10Z

create page

New page

=== Part A ===

The problem explicitly states that T is a "minimum weight connected subset", not "minimum weight connected subset with exactly N-1 edges", so it doesn't have to be an MST. If all weights are positive or zero, then T happens to be the same as the MST, but if negative weights are allowed, all negative weight edges must be included in T to drive the total as low as possible.

=== Part B ===

The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.

← Older revision		Revision as of 08:13, 23 July 2020
Line 8:		Line 8:
	=== Part B ===		=== Part B ===
	The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.		The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.
		+
		+	----
		+	=== Part B alternative solution ===
		+	<pre>
		+	DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight
		+	I. If there are no edges with a negative weight, then return MIN_E
		+	- If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight
		+	- A subgraph of 1 edge is connected
		+
		+	II. If there are edges with a negative weight, then apply the Kruskal's algorithm
		+	- Sort edges by their weight
		+	- For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0
		+	- Maintaining pointer MIN on the component with the lowest weight
		+	- Loop over all edges
		+	- - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue
		+	- - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue
		+	- - - Union with positive component via a positive edge can only increase weight, so the edge is skipped
		+	- - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components
		+	- - - At this step, the algorithm does union 2 components with a negative weight via positive edge
		+	- - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used
		+	- - - If the weight of the combined component is less than MIN, update MIN
		+	- return MIN
		+	</pre>
		+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 14:47, 22 July 2020 (UTC)

← Older revision		Revision as of 22:52, 22 July 2020
Line 8:		Line 8:
	=== Part B ===		=== Part B ===
	The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.		The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.
−
−	~~----~~
−	~~=== Part B alternative solution ===~~
−	~~<pre>~~
−	~~DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight~~
−	~~I. If there are no edges with a negative weight, then return MIN_E~~
−	~~- If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight~~
−	~~- A subgraph of 1 edge is connected~~
−
−	~~II. If there are edges with a negative weight, then apply the Kruskal's algorithm~~
−	~~- Sort edges by their weight~~
−	~~- For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0~~
−	~~- Maintaining pointer MIN on the component with the lowest weight~~
−	~~- Loop over all edges~~
−	~~- - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue~~
−	~~- - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue~~
−	~~- - - Union with positive component via a positive edge can only increase weight, so the edge is skipped~~
−	~~- - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components~~
−	~~- - - At this step, the algorithm does union 2 components with a negative weight via positive edge~~
−	~~- - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used~~
−	~~- - - If the weight of the combined component is less than MIN, update MIN~~
−	~~- return MIN~~
−	~~</pre>~~
−	~~--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 14:47, 22 July 2020 (UTC)~~

← Older revision		Revision as of 14:47, 22 July 2020
Line 8:		Line 8:
	=== Part B ===		=== Part B ===
	The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.		The easiest is just to run a preprocessing pass before running Kruskal's algorithm. Add all edges with negative weight, and all nodes connected to those edges. Then run Kruskal's algorithm normally until it is finished.
		+
		+	----
		+	=== Part B alternative solution ===
		+	<pre>
		+	DFS on a graph to determine whether it contains edges with a negative weight, maintaining pointer MIN_E to one edge with the lowest non-negative weight
		+	I. If there are no edges with a negative weight, then return MIN_E
		+	- If all edges have a non-negative weight, then the minimum weight subset is the subset of 1 edge with the lowest weight
		+	- A subgraph of 1 edge is connected
		+
		+	II. If there are edges with a negative weight, then apply the Kruskal's algorithm
		+	- Sort edges by their weight
		+	- For each connectivity component, the total weight is stored in its representative, representative's weight updates in disjoint_set's union function, initial weight = 0
		+	- Maintaining pointer MIN on the component with the lowest weight
		+	- Loop over all edges
		+	- - If edge's weight is negative, union components, if united component's weight is less than MIN, update MIN, continue
		+	- - If edge's weight is positive and at least one of the components for union has a non-negative weight, continue
		+	- - - Union with positive component via a positive edge can only increase weight, so the edge is skipped
		+	- - If edge's weight is positive, weights of both components for union are negative, and (edges weight + weight of each component is negative), union components
		+	- - - At this step, the algorithm does union 2 components with a negative weight via positive edge
		+	- - - The weight of the combined component is less than the weight of each component separately, even though an edge with a positive weight was used
		+	- - - If the weight of the combined component is less than MIN, update MIN
		+	- return MIN
		+	</pre>
		+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 14:47, 22 July 2020 (UTC)

@@ Line 1: / Line 1: @@
 === Part A ===
 The problem explicitly states that T is a "minimum weight connected subset", not "minimum weight connected subset with exactly N-1 edges", so it doesn't have to be an MST.  If all weights are positive or zero, then T happens to be the same as the MST, but if negative weights are allowed, all negative weight edges must be included in T to drive the total as low as possible.
 === Part B ===
 The easiest is just to run a preprocessing pass before running Kruskal's algorithm.  Add all edges with negative weight, and all nodes connected to those edges.  Then run Kruskal's algorithm normally until it is finished.