Fix comparison in set used by Prim's algorithm

jakobkogler · jakobkogler · commit 9a3d4b84be87 · 2020-03-12T20:35:06.000+01:00
Fixes #527 If the set only compares the weight, then two different edges with the same weight compare equal, and therefor only one of them gets inserted into the set. By comparing also the target node, we fix the problem.
diff --git a/src/graph/mst_prim.md b/src/graph/mst_prim.md
@@ -159,7 +159,7 @@ const int INF = 1000000000;
 struct Edge {
     int w = INF, to = -1;
     bool operator<(Edge const& other) const {
-        return w < other.w;
+        return make_pair(w, to) < make_pair(other.w, other.to);
     }
 };
 

Original file line number	Diff line number	Diff line change
`@@ -159,7 +159,7 @@ const int INF = 1000000000;`
`159`	`159`	`struct Edge {`
`160`	`160`	`int w = INF, to = -1;`
`161`	`161`	`bool operator<(Edge const& other) const {`
`162`		`- return w < other.w;`
	`162`	`+ return make_pair(w, to) < make_pair(other.w, other.to);`
`163`	`163`	`}`
`164`	`164`	`};`
`165`	`165`