From dd5332cbfe57f85ce48934cdac2c9f68c514b436 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <dcariotti24@gmail.com>
Date: Sun, 8 Oct 2017 08:28:27 +0200
Subject: Create dijkstra.cc

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

(limited to 'cpp')

diff --git a/cpp/dijkstra.cc b/cpp/dijkstra.cc
new file mode 100644
index 0000000..8fed8c0
--- /dev/null
+++ b/cpp/dijkstra.cc
@@ -0,0 +1,74 @@
+#include <iostream>
+#include <utility>
+#include <list>
+#include <vector>
+#include <queue>
+#include <fstream>
+using namespace std;
+#define INF 999999
+
+typedef pair<int, int> pii;
+
+list<pii> adj[INF];
+int V; 
+vector<int> previous(INF, -1);
+int dijkstra(int src, int dest) {
+	priority_queue<pii, vector<pii>, greater<pii> > pq;
+	
+	vector<int> dist(INF, INF);
+  previous.resize(V);
+	pq.push(make_pair(0, src));
+	dist[src] = 0;
+	while(!pq.empty()) {
+		int u = pq.top().second;
+		pq.pop();
+
+		for(auto const& i : adj[u]) {
+			int v = i.first;
+			int w = i.second;
+
+			if(dist[v] > dist[u] + w) {
+				dist[v] = dist[u] + w;
+				pq.push({dist[v], v});
+				previous[v] = u;
+			}
+		}
+	}
+
+	return dist[dest];
+}
+
+void dijShortPath(int v, list<int>& path) {
+/* example:
+v = 6;
+v = previous[6] (5)
+v = previous[5] (2)
+...
+*/
+	for(; v != -1; v = previous[v])
+		path.push_front(v);
+}
+
+int main() {
+/*
+numVertici numArchi
+sorgente destinazione
+vertice1 vertice2 peso
+...
+*/
+	cin >> V;
+	int e, sorg, dest;
+	cin >> e >> sorg >> dest;
+	int u, v, w;
+	for(int i = 0; i < e; i++) {
+		cin >> u >> v >> w;
+		adj[u].push_back(make_pair(v, w));
+	}
+	cout << dijkstra(sorg, dest) << endl;
+	list<int> path;
+	dijShortPath(dest, path);
+	for(auto const& i : path)
+		cout << i << ' ';
+
+	return 0;
+}
-- 
cgit v1.2.3-18-g5258