From f12e0947b27d5d66983d9ce2f0ad2732fbb373c9 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 23:14:19 +0100
Subject: Algorithms : complete 03-algorithms_on_graphs 04-paths_in_graphs

---
 .../04-paths_in_graphs/01-dijkstra/dijkstra.cpp    | 35 ++++++++--
 .../02-negative_cycle/negative_cycle.cpp           | 52 +++++++++++++--
 .../03-shortest_paths/shortest_paths.cpp           | 74 ++++++++++++++++++++--
 3 files changed, 146 insertions(+), 15 deletions(-)

diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp
index 757a6c6..7b852e5 100644
--- a/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/01-dijkstra/dijkstra.cpp
@@ -1,15 +1,38 @@
 #include <iostream>
+#include <limits>
 #include <vector>
 #include <queue>
 
 using std::vector;
-using std::queue;
-using std::pair;
 using std::priority_queue;
 
-int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
-  //write your code her
-  return -1;
+int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t)
+{
+    vector<int> dists(adj.size(), std::numeric_limits<int>::max());
+
+    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
+
+    dists[s] = 0;
+    pq.push(s);
+
+    while(!pq.empty()) {
+        int n = pq.top();
+        int dist = dists[n];
+        /* std::cout << " pop: " << n + 1 << " : " << dist << std::endl; */
+        pq.pop();
+
+        for (int i = 0; i < adj[n].size(); i++) {
+            int a = adj[n][i];
+            int nd = dist + cost[n][i];
+            if (dists[a] > nd) {
+                dists[a] = nd;
+                /* std::cout << " push: " << a + 1 << " : " << dists[a].first << std::endl; */
+                pq.push(a);
+            }
+        }
+    }
+
+    return (dists[t] == std::numeric_limits<int>::max() ? -1 : dists[t]);
 }
 
 int main() {
@@ -26,5 +49,5 @@ int main() {
   int s, t;
   std::cin >> s >> t;
   s--, t--;
-  std::cout << distance(adj, cost, s, t);
+  std::cout << distance(adj, cost, s, t) << '\n';
 }
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp
index a48ee97..ecb1ac1 100644
--- a/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/02-negative_cycle/negative_cycle.cpp
@@ -1,11 +1,55 @@
 #include <iostream>
+#include <limits>
 #include <vector>
 
 using std::vector;
 
-int negative_cycle(vector<vector<int> > &adj, vector<vector<int> > &cost) {
-  //write your code here
-  return 0;
+bool bf(vector<vector<int> > &adj, vector<vector<int> > &cost, int source)
+{
+    vector<int> dists(adj.size(), std::numeric_limits<int>::max());
+
+    bool changed = false;
+    bool twice = false;
+    dists[source] = 0;
+
+    for (int i = 0; i <= adj.size(); i++) {
+        changed = false;
+        for (int n = 0; n < adj.size(); n++) {
+            int dist = dists[n];
+            /* std::cout << n + 1 << " : " << dist << std::endl; */
+            if (dist != std::numeric_limits<int>::max()) {
+                for (int j = 0; j < adj[n].size(); j++) {
+                    int a = adj[n][j];
+                    int nd = dist + cost[n][j];
+                    if (dists[a] > nd) {
+                        /* std::cout << "   " << a + 1 << " : " << nd << std::endl; */
+                        dists[a] = nd;
+                        changed = true;
+                    }
+                }
+            }
+        }
+        if (!changed) {
+            /* std::cout << "changed ..." << std::endl; */
+            if (twice){
+                /* std::cout << "break" << std::endl; */
+                break;
+            }
+            twice = true;
+        }
+    }
+
+    return changed;
+}
+
+int negative_cycle(vector<vector<int> > &adj, vector<vector<int> > &cost)
+{
+    for (int i = 0; i < adj.size(); i++) {
+        if (bf(adj, cost, i))
+            return 1;
+    }
+    return 0;
+
 }
 
 int main() {
@@ -19,5 +63,5 @@ int main() {
     adj[x - 1].push_back(y - 1);
     cost[x - 1].push_back(w);
   }
-  std::cout << negative_cycle(adj, cost);
+  std::cout << negative_cycle(adj, cost) << '\n';
 }
diff --git a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp
index ac2007e..cb12bcd 100644
--- a/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp
+++ b/03-algorithms_on_graphs/04-paths_in_graphs/03-shortest_paths/shortest_paths.cpp
@@ -5,11 +5,75 @@
 
 using std::vector;
 using std::queue;
-using std::pair;
-using std::priority_queue;
 
-void shortest_paths(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, vector<long long> &distance, vector<int> &reachable, vector<int> &shortest) {
-  //write your code here
+bool relax(vector<vector<int> > &adj, vector<vector<int> > &cost, int n, vector<long long> &dists)
+{
+    bool relaxed = false;
+    long long dist = dists[n];
+    if (dist != std::numeric_limits<long long>::max()) {
+        for (int j = 0; j < adj[n].size(); j++) {
+            int a = adj[n][j];
+            long long nd = dist + cost[n][j];
+            if (dists[a] > nd) {
+                dists[a] = nd;
+                relaxed = true;
+            }
+        }
+    }
+    return relaxed;
+}
+
+bool bf(vector<vector<int> > &adj, vector<vector<int> > &cost, int source, vector<long long> &dists, queue<int> &q)
+{
+    bool changed = false;
+    bool twice = false;
+    dists[source] = 0;
+
+    for (int i = 0; i < adj.size(); i++) {
+        changed = false;
+        for (int n = 0; n < adj.size(); n++) {
+            if (relax(adj, cost, n, dists))
+                changed = true;
+        }
+        if (!changed) {
+            if (twice)
+                return false;
+            twice = true;
+        }
+    }
+
+    for (int n = 0; n < adj.size(); n++) {
+        if (relax(adj, cost, n, dists))
+            q.push(n);
+    }
+
+    return true;
+}
+
+void shortest_paths(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, vector<long long> &distance, vector<int> &reachable, vector<int> &shortest)
+{
+    queue<int> q;
+
+    bool has_neg_loops = bf(adj, cost, s, distance, q);
+
+    for (int i = 0; i < adj.size(); i++)
+        if (distance[i] == std::numeric_limits<long long>::max())
+            reachable[i] = 0;
+
+    if (!has_neg_loops)
+        return;
+
+    while(!q.empty()) {
+        int n = q.front();
+        q.pop();
+        shortest[n] = 0;
+        for (int j = 0; j < adj[n].size(); j++) {
+            int a = adj[n][j];
+            if (shortest[a] == 1)
+                q.push(a);
+        }
+
+    }
 }
 
 int main() {
@@ -26,7 +90,7 @@ int main() {
   std::cin >> s;
   s--;
   vector<long long> distance(n, std::numeric_limits<long long>::max());
-  vector<int> reachable(n, 0);
+  vector<int> reachable(n, 1);
   vector<int> shortest(n, 1);
   shortest_paths(adj, cost, s, distance, reachable, shortest);
   for (int i = 0; i < n; i++) {
-- 
cgit v1.1-2-g2b99