Laba 5

gistfile1.txt

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int INF = 99999999;

void BellmanFord(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
    // Bellman-Ford
    d[k] = 0;
    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < static_cast<int>(g.size()); j++)
            if(d[g[j].first] < INF)
                d[g[j].second.first] = min(d[g[j].second.first], d[g[j].first] + g[j].second.second);

}

void Dijkstra(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
    vector<bool> used(n, false);
    used[k] = true;
    d[k] = 0;
    set<pair<int, int>> q;
    q.insert(make_pair(0, k));
    while(q.size() > 0) {
        pair<int, int> top = *q.begin();
        q.erase(top);

        for(int i = 0; i < static_cast<int>(g.size()); i++)
            if(g[i].first == top.second && !used[g[i].second.first]) {
		q.erase(make_pair(d[g[i].second.first], g[i].second.first));                
		d[g[i].second.first] = top.first + g[i].second.second;
                q.insert(make_pair(d[g[i].second.first], g[i].second.first));
                used[g[i].second.first] = true;
            }
    }
}

bool CalcDistanceWithBellmanFord(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
    d.assign(n, INF);
    BellmanFord(g, d, n, k);

    // check for negative cycles
    bool had_neg_cyc = false;
    for(int i = 0; i < static_cast<int>(g.size()); i++)
        if(d[g[i].second.first] > d[g[i].first] + g[i].second.second) {
            had_neg_cyc = true;
            break;
        }
    return !had_neg_cyc;
}

bool CalcDistanceWithDijkstra(vector<pair<int, pair<int, int> > >& g, vector<int>& d, int n, int k) {
    // check for negative edges not incedent with k
    bool had_negative_edges = false;
    for(int i = 0; i < static_cast<int>(g.size()); i++)
        if(g[i].second.second < 0 && g[i].first != k) {
            had_negative_edges = true;
            break;
        }

    if(had_negative_edges) return false;

    d.assign(n, INF);
    Dijkstra(g, d, n, k);
    return true;
}

int GetEdge(const vector<pair<int, pair<int, int> > >& g, int u, int v) {
    for(int i = 0; i < static_cast<int>(g.size()); i++)
        if(g[i].first == u && g[i].second.first == v)
            return g[i].second.second;
    return -1;
}

int main() {
    //cout << "n, m? :" << endl;
    int n, m;
    cin >> n >> m;
    vector<pair<int, pair<int, int> > > g;
    int u, v, w;
    for(int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        u--;
        v--;
        g.push_back(make_pair(u, make_pair(v, w)));
    }

    //cout << "k?" << endl;
    int k;
    cin >> k;
    k--;
    vector<int> d;

    // calc distance from k to all
    bool success = CalcDistanceWithBellmanFord(g, d, n, k);
    if(success) {
        cout << "distance vector(Bellman-Ford): " << endl;
        for (auto x : d)
            if(x != INF)
                cout << x << " ";
            else
                cout << "F" << " ";
        cout << endl;
    } else {
        cout << "We have negative cycles" << endl;
    }

    // calc distance from u to v
    //cout << "u, v?" << endl;
    cin >> u >> v;
    u--;
    v--;

    // check if exist edge (u, v)
    w = GetEdge(g, u, v);
    if(w > 0) {
        cout << "distance from " << u + 1 << " to " << v + 1 << " = " << w << endl;

    } else {
        // calc distance with Bellman-Ford
        success = CalcDistanceWithBellmanFord(g, d, n, u);
        if (success)
            cout << "distance from" << u + 1 << " to " << v + 1 << " = " << d[v] << endl;
        else
            cout << "can't calc distance" << endl;
    }

    // calc distance matrix from k
    success = CalcDistanceWithDijkstra(g, d, n, k);
    if(success) {
        cout << "distance vector(Dijkstra): " << endl;
        for (auto x : d)
            if(x != INF)
                cout << x << " ";
            else
                cout << "F" << " ";
        cout << endl;
    } else {
        cout << "graph had negative edges which not incedent with start vertrex" << endl;
    }

    // calc distance from u to v
    //cout << "u, v?" << endl;
    cin >> u >> v;
    u--;
    v--;
    w = GetEdge(g, u, v);
    if(w > 0) {
        cout << "distance from " << u + 1 << " to " << v + 1 << " = " << w << endl;
    } else {
        // calc distance with Dijkstra
        success = CalcDistanceWithDijkstra(g, d, n, u);
        if (success)
            cout << "distance from " << u + 1 << " to " << v + 1 << " = " << d[v] << endl;
        else
            cout << "can't calc distance" << endl;

    }
    return 0;
}