From 69c98b39106cc2776f6a4983e548338ac24b5e84 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Wed, 27 Nov 2024 15:36:04 +0100
Subject: simplify dijkstra

---
 content/graph/dijkstra.cpp | 31 ++++++++++++++-----------------
 test/graph/dijkstra.cpp    | 12 ++++++------
 2 files changed, 20 insertions(+), 23 deletions(-)

diff --git a/content/graph/dijkstra.cpp b/content/graph/dijkstra.cpp
index 4c1c9d8..ab4bef9 100644
--- a/content/graph/dijkstra.cpp
+++ b/content/graph/dijkstra.cpp
@@ -1,21 +1,18 @@
-using path = pair<ll, int>; //dist, destination
+using Dist = ll;
 
-auto dijkstra(const vector<vector<path>>& adj, int start) {
-	priority_queue<path, vector<path>, greater<path>> pq;
-	vector<ll> dist(ssize(adj), INF);
-	vector<int> prev(ssize(adj), -1);
-	dist[start] = 0; pq.emplace(0, start);
+auto dijkstra(vector<vector<pair<int, Dist>>> &adj, int start) {
+	priority_queue<pair<Dist, int>> pq;
+	vector<Dist> dist(ssize(adj), INF);
+	dist[start] = 0, pq.emplace(0, start);
 
-	while (!pq.empty()) {
-		auto [dv, v] = pq.top(); pq.pop();
-		if (dv > dist[v]) continue; // WICHTIG!
+	while (!empty(pq)) {
+		auto [du, u] = pq.top();
+		du = -du, pq.pop();
+		if (du > dist[u]) continue; // WICHTIG!
 
-		for (auto [du, u] : adj[v]) {
-			ll newDist = dv + du;
-			if (newDist < dist[u]) {
-				dist[u] = newDist;
-				prev[u] = v;
-				pq.emplace(dist[u], u);
-	}}}
-	return dist; //return prev;
+		for (auto [v, d]: adj[u]) {
+			Dist dv = du + d;
+			if (dv < dist[v]) dist[v] = dv, pq.emplace(-dv, v);
+	}}
+	return dist;
 }
diff --git a/test/graph/dijkstra.cpp b/test/graph/dijkstra.cpp
index c0cfb7e..18420ac 100644
--- a/test/graph/dijkstra.cpp
+++ b/test/graph/dijkstra.cpp
@@ -13,21 +13,21 @@ void stress_test() {
 		int n = Random::integer<int>(2, 30);
 		int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1)));
 
-		vector<vector<path>> adj(n);
+		vector<vector<pair<int, ll>>> adj(n);
 		vector<edge> edges;
 
 		Graph<NoData, true> g(n);
 		g.erdosRenyi(m);
 		g.forEdges([&](int a, int b){
 			ll w = Random::integer<ll>(1, 1'000'000'000'000ll);
-			adj[a].push_back({w, b});
+			adj[a].emplace_back(b, w);
 			edges.push_back({a, b, w});
 		});
 
 		for (int i = 0; i < n; i++) {
 			auto got = dijkstra(adj, i);
 			auto expected = bellmannFord(n, edges, i);
-			
+
 			if (got != expected) cerr << "error" << FAIL;
 			queries += n;
 		}
@@ -41,12 +41,12 @@ void performance_test() {
 	timer t;
 	Graph<NoData> g(N);
 	g.erdosRenyi(M);
-	vector<vector<path>> adj(N);
+	vector<vector<pair<int, ll>>> adj(N);
 	g.forEdges([&](int a, int b){
 		ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll);
 		ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll);
-		adj[a].push_back({w1, b});
-		adj[b].push_back({w2, a});
+		adj[a].emplace_back(b, w1);
+		adj[b].emplace_back(a, w2);
 	});
 
 	t.start();
-- 
cgit v1.2.3