Algoritmul Bellman-Ford în C++ (infoarena)

Salutare și bine v-am găsit la un nou tutorial. Astăzi vom vorbi despre algoritmul Bellman-Ford și vom rezolva problema de pe arhiva educațională a site-ului infoarena.

Enunț:

Se dă un graf orientat conex cu N noduri şi M muchii cu costuri. Definim un lanţ ca fiind un şir de noduri cu proprietatea că între oricare două consecutive există o muchie. Costul unui lanţ este dat de suma costurilor muchiilor care unesc nodurile ce îl formează. Definim un ciclu ca fiind un lanţ cu proprietatea că primul element al său este egal cu ultimul.

Graful este următorul:

În mod normal suntem tentați să folosim Algoritmul lui Dijkstra, dar din păcate el funcționează doar pe grafuri orientate cu costuri pozitive. De aceea  va trebui să folosim algoritmul Bellman-Ford. Funcționează la fel ca și Dijkstra, dar are mici diferențe. Dacă se găsește însă un circuit negativ, atunci nu există soluție (pentru că drumul ar fi minimizat la maxim) .  Algoritmul minimizează drumul de la nodul de start  la oricare vârf x până la obținerea costului minim. Costurile se rețin într-un vector d , iar pentru fiecare arc (j,k) se verifică dacă minimizează distanța de la nodul de start la nodul x  (d[x] > d[j] + cost[j][x] ), iar această operație se repetă de n ori. Pentru a obține 100 de puncte , îmbunătăţirea costului nodurilor vecine  se face introducându-le într-o coadă în cazul scăderii costului, dacă nu apar deja.

Mai jos aveți codul sursă

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
vector< pair<int, int> >graf[50005];
vector <int> v;
queue <int> coada;
int d[50005];
int viz[50005];
int esteincoada[50005];
bool bellmanford(int s)
{
    for(int i=1;i<=n;i++)
    {
        viz[i]=0;
        esteincoada[i]=0;
        d[i]=INF;
    }
    d[s] = 0;
    coada.push(s);
    esteincoada[s] = 1;

    while(!coada.empty())
    {
        int nodcurent = coada.front();
        viz[nodcurent]++;
        if(viz[nodcurent] >= n)
            return false;
        coada.pop();
        esteincoada[nodcurent] = 0;

        for(size_t i=0;i<graf[nodcurent].size();i++)
        {
            int vecin = graf[nodcurent][i].first;
            int cost = graf[nodcurent][i].second;
            if(d[nodcurent]+cost < d[vecin])
            {
                d[vecin] = d[nodcurent]+cost;
                if(!esteincoada[vecin])
                    coada.push(vecin);
            }
        }
    }
    return true;
}
int main()
{in>>n>>m;
for(int i=1;i<=m;i++)
{
    int x,y,c;
    in>>x>>y>>c;
    graf[x].push_back(make_pair(y,c));
}
  if(bellmanford(1))
    {
        for(int i=2;i<=n;i++)
            out<<d[i]<<" ";
    }
    else
      out<<"Ciclu negativ!";



    return 0;
}