diff options
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++) { |