# Cod sursa(job #2809118)

Utilizator Data 26 noiembrie 2021 00:17:59 Algoritmul Bellman-Ford 0 cpp-64 done Arhiva educationala 4.47 kb
``````#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream fapm("apm.in");
ofstream gapm("apm.out");

ifstream fbf("bellmanford.in");
ofstream gbf("bellmanford.out");

class Graf
{
int nrNoduri;
int nrMuchii;

vector<vector<pair<int,int>>> costs;
vector<tuple<int,int,int>> edge;

public:

//void citire_apm();
Graf(int n, int m, int type);
void APM();
int nodCostMin(vector<int> &helper, vector<bool> &inMst);
void BF();

};

Graf::Graf(int n, int m, int type)
{

this->nrNoduri = n;
this->nrMuchii = m;

if(type == 1)       ///type = 1 -> pt apm
{
this->costs.resize(nrNoduri + 1);

int nod1, nod2, cost;
pair<int,int> temp;

for(int i = 0; i < this->nrMuchii; i++)
{
fapm>>nod1>>nod2>>cost;

temp.first = nod2;
temp.second = cost;

this->costs[nod1].push_back(temp);
temp.first = nod1;
this->costs[nod2].push_back(temp);
}
}
else
{
this->edge.resize(nrNoduri + 1);

int nod1, nod2, cost;
tuple<int,int,int> temp;

//cout<<"test1\n";

for(int i = 0; i < this->nrMuchii; i++)
{
fbf>>nod1>>nod2>>cost;
temp = make_tuple(nod1,nod2,cost);
edge[i] = temp;
}

//cout<<"test2\n";
}

}

/*void Graf::citire_apm()
{
costs.resize(nrNoduri + 1);
int nod1, nod2, cost;
pair<int,int> temp;

fapm>>nrNoduri>>nrMuchii;

for(int i = 0; i < nrMuchii; i++)
{
fapm>>nod1>>nod2>>cost;

temp.first = nod2;
temp.second = cost;

costs[nod1].push_back(temp);
temp.first = nod1;
costs[nod2].push_back(temp);
}

}*/

int Graf::nodCostMin(vector<int> &helper, vector<bool> &inMst)
{
int minimum, indexOfMin;
minimum  = INT_MAX;

for(int i = 1; i <= nrNoduri; i++)
if(inMst[i] == false && helper[i] < minimum)
{
minimum = helper[i];
indexOfMin = i;
}

return indexOfMin;
}
void Graf::APM()
{
vector<int> parent;         //un fel de vector de tati, aici va fi apm-ul
vector<bool> inMst;         //un fel de visited
vector<int> helper;         //cele mai mici costuri din nodul curent
//se updateaza la fiecare pas

for(int i = 0 ; i <= nrNoduri; i++)
{
helper.push_back(INT_MAX);
inMst.push_back(false);
parent.push_back(0);
}

helper[1] = 0;
parent[1] = -1;
for(int i = 1 ; i <= nrNoduri; i++)
{
int nextVertex = nodCostMin(helper, inMst);  //gasim urmatorul nod cu muchia de cost minim
inMst[nextVertex] = true;

int sz = costs[nextVertex].size();
for(int j = 0; j < sz; j++)
{
int temp1 = costs[nextVertex][j].first;
int temp2 = costs[nextVertex][j].second;

if(inMst[temp1] == false && temp2 < helper[temp1])
{
parent[temp1] = nextVertex;
helper[temp1] = temp2;
}

}

}
int sum = 0;
for(int  i = 2; i <= nrNoduri; i++)
sum += helper[i];

gapm<<sum<<"\n";
gapm<<nrNoduri - 1<<"\n";
for(int  i = 2; i <= nrNoduri; i++)
gapm<<parent[i]<<" "<<i<<"\n";

}

void Graf::BF()
{
vector<int> distances(nrNoduri + 1, INT_MAX);

distances[1] = 0;

for(int  i = 1; i <= nrNoduri; i++)
{
for(int j = 0; j < nrMuchii; j++)
{

int temp1 = get<0>(edge[j]);
int temp2 = get<1>(edge[j]);
int cost = get<2>(edge[j]);

if(distances[temp1] != INT_MAX && distances[temp1] + cost < distances[temp2])
distances[temp2] = distances[temp1] + cost;

}

}

for(int i = 0; i < nrMuchii; i++)
{
int temp1 = get<0>(edge[i]);
int temp2 = get<1>(edge[i]);
int cost = get<2>(edge[i]);

if(distances[temp1]!= INT_MAX && distances[temp1] + cost < distances[temp2])
{
gbf<<"Ciclu negativ!";
return;
}

}

for(int i = 2; i <= nrNoduri; i++)
gbf<<distances[i]<<" ";
}

int main()
{
int n, m;
fbf>>n>>m;

//Graf G(n, m, 1);
//G.APM();
Graf G(n, m, 2);
G.BF();

return 0;
}
``````