From 53e7f12d828bb94c05d2b6c4e04d61de9482c426 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Thu, 3 Dec 2015 01:12:26 +0100
Subject: Improving graoh chapter.

---
 graph/dijkstra.cpp | 36 +++++++++++++++++++++---------------
 1 file changed, 21 insertions(+), 15 deletions(-)

(limited to 'graph/dijkstra.cpp')

diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
index 1d4f7a1..649cf6e 100644
--- a/graph/dijkstra.cpp
+++ b/graph/dijkstra.cpp
@@ -1,20 +1,26 @@
-priority_queue<ii, vector<ii>, greater<ii> > pq;
-vector<int> dist;
-dist.assign(NUM_VERTICES, INF);
-dist[START] = 0;
-pq.push(ii(0, START));
+// Laufzeit: O((|E|+|V|)*log |V|) 
+void dijkstra(int start) {
+	priority_queue<ii, vector<ii>, greater<ii> > pq;
+	vector<int> dist, parent;
+	dist.assign(NUM_VERTICES, INF);
+	parent.assign(NUM_VERTICES, -1);
 
-while (!pq.empty()) {
-	ii front = pq.top(); pq.pop();
-	int curNode = front.second, curDist = front.first;
-	
-	if (curDist > dist[curNode]) continue;
-	
-	for (int i = 0; i < (int)adjlist[curNode].size(); i++) {
-		int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second;
+	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 (nextDist < dist[nextNode]) {
-			dist[nextNode] = nextDist; pq.push(ii(nextDist, nextNode));
+		for (int i = 0; i < (int)adjlist[curNode].size(); i++) {
+			int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second;
+			
+			if (nextDist < dist[nextNode]) {
+				dist[nextNode] = nextDist; parent[nextNode] = curNode;
+				pq.push(ii(nextDist, nextNode));
+			}
 		}
 	}
 }
-- 
cgit v1.2.3