diff options
| -rw-r--r-- | Year_2/Algorithms/bellman-ford.cc | 167 |
1 files changed, 167 insertions, 0 deletions
diff --git a/Year_2/Algorithms/bellman-ford.cc b/Year_2/Algorithms/bellman-ford.cc new file mode 100644 index 0000000..0942646 --- /dev/null +++ b/Year_2/Algorithms/bellman-ford.cc @@ -0,0 +1,167 @@ +#include <fstream> +#include <iostream> +#include <map> +#include <vector> +#define INF 9999999 + +using namespace std; + +template <class H> +class Graph { +public: + Graph<H>* + add_node(H u) + { + auto it = nodes_.find(u); + + if (it == nodes_.end()) { + nodes_.insert({ u, vector<pair<H, int>>() }); + size_++; + } + + return this; + } + + Graph<H>* + add_edge(H u, H v, int w) + { + auto i = nodes_.find(u); + auto j = nodes_.find(v); + + if (i != nodes_.end() && j != nodes_.end()) { + nodes_[u].push_back({ v, w }); + edges_.push_back({ u, v, w }); + } + + return this; + } + + void + bellmanford(H s, H r, ostream& out) + { + map<H, int> dist; + map<H, pair<H, int>> p; + + for (const auto& it : nodes_) { + dist.insert({ it.first, INF }); + } + + dist[s] = 0; + + for (size_t i = 0; i < size_; ++i) { + for (const auto& e : edges_) { + auto u = get<0>(e); + auto v = get<1>(e); + auto w = get<2>(e); + + if (dist[u] != INF && dist[u] + w < dist[v]) { + dist[v] = dist[u] + w; + p[v] = make_pair(u, dist[v]); + } + } + } + + for (size_t i = 0; i < size_; ++i) { + for (const auto& e : edges_) { + auto u = get<0>(e); + auto v = get<1>(e); + auto w = get<2>(e); + + if (dist[u] != INF && dist[u] + w < dist[v]) { + out << "undef." << endl; + return; + } + } + } + + if (p.find(r) == p.end()) { + out << "inf." << endl; + return; + } else { + out << p[r].second << endl; + } + } + +private: + // `nodes_` is map which has the node as key and the edges as value. + // eg: + // nodes_[0] = [[1, 300]]; + // there is an edge 0<->1 with 300 as weight + map<H, vector<pair<H, int>>> nodes_; + + vector<tuple<H, H, int>> edges_; + + size_t size_ { 0 }; +}; + +int +main(int argc, char** argv) +{ + int ts = (argc > 1) ? stoi(argv[1]) : 100; + int n, m; + string tp; + string ch; + ifstream fin("input.txt"); + ofstream fout("output.txt"); + + for (int i = 0; i < ts; ++i) { + fin >> n >> m >> tp; + + if (tp == "int") { + Graph<int>* g = new Graph<int>(); + int k, n1, n2, s, r; + int w; + + for (int j = 0; j < n; ++j) { + fin >> k; + g->add_node(k); + } + + for (int j = 0; j < m; ++j) { + fin >> ch; + n1 = stoi(ch.substr(1, ch.length())); + fin >> n2; + fin >> ch; + w = stoi(ch.substr(0, ch.length() - 1)); + + g->add_edge(n1, n2, w); + } + + fin >> s >> r; + + g->bellmanford(s, r, fout); + + delete g; + } else if (tp == "double") { + Graph<int>* g = new Graph<int>(); + double k, n1, n2, s, r; + int w; + + for (int j = 0; j < n; ++j) { + fin >> k; + g->add_node(k * 10); + } + + for (int j = 0; j < m; ++j) { + fin >> ch; + n1 = stod(ch.substr(1, ch.length())); + fin >> n2; + fin >> ch; + w = stoi(ch.substr(0, ch.length() - 1)); + + g->add_edge(n1 * 10, n2 * 10, w); + } + + fin >> s >> r; + + g->bellmanford(s * 10, r * 10, fout); + + delete g; + } + } + + fin.close(); + fout.close(); + + return 0; +} |