From fee5322fe37cb270a93c1693e2668e53138f192d Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc75.atis-stud.uni-karlsruhe.de>
Date: Tue, 18 Nov 2014 14:19:42 +0100
Subject: dijkstra

---
 graph/dijkstra.cpp | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)
 create mode 100644 graph/dijkstra.cpp

(limited to 'graph/dijkstra.cpp')

diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
new file mode 100644
index 0000000..e7ec0c3
--- /dev/null
+++ b/graph/dijkstra.cpp
@@ -0,0 +1,20 @@
+priority_queue<ii, vector<ii>, greater<ii> > pq;
+vector<int> dist;
+dist.assign(NUM_VERTICES, INF);
+dist[0] = 0;
+pq.push(ii(0, 0));
+
+while (!pq.empty()) {
+	di front = pq.top(); pq.pop();
+	int curNode = front.second, curDist = front.first;
+	
+	if (curDist > dist[curNode]) continue;
+	
+	for (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; pq.push(ii(nextDist, nextNode));
+		}
+	}
+}
\ No newline at end of file
-- 
cgit v1.2.3