Algorytm Bellmana Forda

Algorytm Bellmana-Forda służy do wyznaczania najkrótszych ścieżek między wierzchołkiem źródłowym s, a wszystkimi pozostałymi wierzchołkami w grafie ważonym i skierowanym (bądź nie), o wagach dowolnych znaków. Jedynym warunkiem działania algorytmu jest niewystępowanie cykli o ujemnych wagach. Dobrze zaimplementowany (tak jak poniżej) algorytm Bellmana-Forda działa w czasie O(V*E) (V-ilosc wierzcholków, E-ilosc krawędzi). Idea tego algorytmu polega na stopniowym ulepszaniu wyniku w kolejnych przebiegach, a sam algorytm jest oparty o metodę relaksacji, która zmniejsza stopniowo w miare przebiegów algorytmu, oszacowanie na wage najkrotszej sciezki ze zrodla s do kazdego wierzcholka v. Algorytm zwraca prawde jesli w grafie nie ma cykli o ujemnych wagach i falsz w przeciwnym wypadku.

Przykładowy kod:

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
 
int N, M, u, v, w; //N-ilosc wierzcholkow; M-ilosc krawedzi
const int INF = 1000000001; //nieskonczonosc
 
struct EDGE{ //struktura reprezentujaca krawedz. Taka reprezentacja grafu jest wygodna w algorytmie Bellmana-Forda
    int u;
    int v;
    int w;
    EDGE(int i, int j, int k){
        u=i;
        v=j;
        w=k;
    }
};
 
vector<EDGE> Edges; //struktura przechowujaca krawedzie
int d[10000]; //struktura przechowujaca dlugosci (d[v]) najkrotszych drog laczacych wierzcholek s z v
int poprzednik[10000]; //przechowuje poprzednik wierzcholka v na sciezce (najkrotszej) do s
int s; //wierzcholek dla ktorego liczymy odleglosci (zrodlo) i do ktorego konstruujemy drogi
 
void init(){ //inicjujemy wszystkie tablice
    for(int i=0; i<N; i++){
        d[i]=INF; //poczatkowo odleglosc kazdego wierzcholka v od zrodla s wynosi nieskoczonosc
        poprzednik[i]=-1; //nikt nie ma zadnych poprzednikow bo nie ma zadnych sciezek
    }
    d[s]=0; //odleglosc zrodla od niego samego wynosi oczywiscie 0
}
 
bool bellman(){ //oblicza dlugosci oraz przebieg najkrotszych sciezek miedzy wierzcholkiem zrodlowym s a wszystkimi innymi wierzcholkami
    for(int i=1; i<N; i++){ //wykonujemy N-1 przebiegow (tyle przebiegow wystarczy zeby obliczyc wszystkie najkrotsze sciezki)
        for(int j=0; j<2*M; j++){ //dla kazdej krawedzi w grafie (w naszym przypadku poniewaz graf jest nieskierowany to krawedzi jest 2M, 
            //bo kazdej krawedzi towarzysszy krawedz odwrotna) ...
            if(d[Edges[j].v] > d[Edges[j].u] + Edges[j].w){ //jezeli dlugosc sciezki s~>v jest wieksza niz s~>u + waga krawedzi u->v to...
                d[Edges[j].v] = d[Edges[j].u] + Edges[j].w; //... zaktualizuj optymalny winik dla v i...
                poprzednik[Edges[j].v]=Edges[j].u; //... ustaw u jako poprzednika v na aktualnej najkrotszej sciezce s~>v
            }
        }
    }
    for(int i=0; i<M; i++){ //sprawdzamy czy w grafie nie ma cyklu o ujemnej wadze, ktory powoduje ze odleglosc wierzcholka v nalezacego do tego cyklu mozna
        //dowolnie zmniejszyc przechodzac przez ten cykl wiele razy (bo cykl ma sume wag krawedzi mniejsza niz zero czyli dziala jak 'zagiecie przestrzeni i czasu' ;D)
        if(d[Edges[i].v] > d[Edges[i].u] + Edges[i].w)return false; //aby to sprawdzic nalezy sprawdzic czy mimo N-1 przebiegow algorytmu (ktore wedlug definicji MUSZA
        //wystarczyc do wyznaczenia minimalnych sciezek), wciaz da sie zmniejszyc odleglosc v od s
    }
    return true; //w grafie nie ma cyklu o ujemnej wadze wiec wyniki sa prawidlowe
}
 
void droga(int v){ //odtwarza droge v~>s idac po poprzednikach na najkrotszej sciezce
    do{
        cout<<v+1<<" ";
        v=poprzednik[v];
    }while(poprzednik[v]!=-1);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin>>N>>M>>s;
    s--;
    for(int i=0; i<M; i++){
        cin>>u>>v>>w;
        Edges.push_back(EDGE(u-1, v-1, w));
        Edges.push_back(EDGE(v-1, u-1, w)); //zakladamy ze graf jest nieskierowany (rowniedobrze moglby byc skierowany, wtedy usun ta linijke)
    }
    init();
    if(!bellman()){ //w grafie wystepuje cykl o ujemnej wadze
        cout<<"W grafie wystepuje cykl o ujemnej wadze i nie da sie obliczyc najkrotszych sciezek.\n";
    }else{
        cout<<"W grafie nie wystepuja cykle o ujemnej wadze. Oto najkrotsze sciezki miedzy wierzcholkiem "<<s+1<<", a wszystkimi pozostalymi:\n";
        for(int i=0; i<N; i++){
            if(i!=s){
                cout<<s+1<<"->"<<i+1<<" dl. "<<d[i]<<", przebieg: ";
                droga(i);
                cout<<s+1<<endl;
            }
        }
    }
    system("pause");
    return 0;
}
 
//Przykladowe wejscie:
/*10 17 1
1 2 13
1 9 33
2 3 27
2 4 1
2 10 8
2 9 9
3 4 10
4 10 11
4 6 2
4 5 3
5 6 9
6 10 666
6 7 66
7 8 333
7 9 33
9 10 3
6 9 15*/