From 7cf8f4e10ac917ed8b900e43e294e26200329ee8 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Thu, 6 Oct 2016 19:44:29 +0200
Subject: Saving space in Dijkstra.

---
 graph/dijkstra.cpp | 12 +++---------
 1 file changed, 3 insertions(+), 9 deletions(-)

(limited to 'graph')

diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
index 1fb5f53..52cb57e 100644
--- a/graph/dijkstra.cpp
+++ b/graph/dijkstra.cpp
@@ -2,22 +2,16 @@
 void dijkstra(int start) {
 	priority_queue<ii, vector<ii>, greater<ii> > pq;
 	vector<int> dist(NUM_VERTICES, INF), parent(NUM_VERTICES, -1);
-
-	dist[start] = 0;
-	pq.push(ii(0, start));
+	dist[start] = 0; pq.push(ii(0, start));
 
 	while (!pq.empty()) {
 		ii front = pq.top(); pq.pop();
 		int curNode = front.second, curDist = front.first;
-		
-		if (curDist > dist[curNode]) continue;
+		if (curDist > dist[curNode]) continue; // WICHTIG!
 		
 		for (auto n : adjlist[curNode]) {
 			int nextNode = n.first, nextDist = curDist + n.second;
 			if (nextDist < dist[nextNode]) {
 				dist[nextNode] = nextDist; parent[nextNode] = curNode;
 				pq.push(ii(nextDist, nextNode));
-			}
-		}
-	}
-}
+}}}}
-- 
cgit v1.2.3