Implementácia

Priamočiara implementácia by asi vyzerala nasledovne:

• Štandardne si vo vector<vector<int> > pre každý vrchol pamätáme, kam sa z neho vieme dostať jednou hranou.
• V poli dlhom $n$ si pre každý vrchol uchovávame jeho vzdialenosť, alebo −1, ak ešte nebol zatopený. Máme vector<vector<int> > M, s rovnakým významom, ako vo vyššie uvedených odsekoch. Postupne zostrojujeme M[0], M[1], M[2], ... a zastavíme sa buď vtedy, keď zatopíme $B$, alebo sa nám v niektorom kole nepodarí zatopiť žiaden nový vrchol.

Posledná časť implementácie zvykne byť ale nahradená elegantnejšou implementáciou s frontou. (Tá nám umožňuje vkladať prvky na jej koniec, alebo vyberať prvky z jej začiatku.)

Hlavným pozorovaním je, že pre korektnosť algoritmu nie je dôležité, v akom presnom poradí sa rozširujeme z vrcholov v $M_k$, ale iba to, že sa to deje skôr, ako rozširovanie sa z $M_{k+1}$. Budeme mať teda frontu, v ktorej budú udalosti typu rozšír sa z vrcholu v. Na začiatku v nej bude iba vrchol $A$, a vždy, keď sa rozšírime z nejakého vrcholu, pridáme na koniec fronty vrcholy, ktoré sme tak zatopili.

Rozmyslite si, že sa naozaj budeme najprv rozširovať z vrcholov vzdialených 0, potom 1, 2, a tak ďalej.

Zastavíme sa buď vtedy, keď zatopíme $B$, alebo keď je fronta prázdna.

int n; // pocet vrcholov  v grafe
int a, b; // odkial chceme ist a kam

// kam[i] obsahuje zoznam vrcholov, do ktorych sa vieme dostat z i
vector<vector<int> > kam;

... // nacitame graf

if (a == b) { // specialny pripad
    cout << "0\n";
    return 0;
}

vector<int> vzdialenost(n, -1);
queue<int> fronta;

fronta.push(a);
vzdialenost[a] = 0;
while (!fronta.empty()) {
    int v = fronta.front();
    fronta.pop();
    for (int i = 0; i < (int) kam[v].size(); i++) {
        int w = kam[v][i];
        if (vzdialenost[w] != -1) {
        continue;
        }
        vzdialenost[w] = vzdialenost[v] + 1;
        if (w == b) {
        cout << vzdialenost[w] << "\n";
        return 0;
        }
        fronta.push(w);
    }
}