C/C++ algorytm Bellmana Forda ujemny cykl

Witam serdecznie!
Mam problem z algorytmem wyszukującym najkrótszą ścieżkę.
Chodzi mi dokładnie o to, by wykryć czy w grafie znajduje się ujemny cykl.
O to mój kod, testowałem, na różnych grafach i działa poprawnie.

 
#include <cstdlib> 
#include <fstream>
#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;
#define MAX 99999
void BellmanFord(int, int, int**);
void wyswietl(int ,int**);
void wyswietl_BellmanFord(int*, int*, int, int);


int main()
{
	
    int l_wierzch; l_wierzch = 6;

    int wierzch_start =0;
    int ** macierz;
    macierz = new int * [l_wierzch];
    for(int i=0; i<l_wierzch; i++)
        macierz[i] = new int[l_wierzch];

    
	int macierz2[6][6]={{0, 5, 0, 0, 0, 0},
				    {0, 0, 0, 3, 9, 0},
				    {3,-4, 0, 0, 0, 0},
				    {0, 0, 0, 0, 3, 2},
				    {0 ,0 ,-1,0, 0,-5},
				    {9, 0, 8, 0, 0, 0},
						          };
	for(int j=0; j<l_wierzch; j++)
	{
        for(int k=0; k<l_wierzch; k++)
		{
			
				macierz[j][k] = macierz2[j][k];
		}
	}
    //
    wyswietl(l_wierzch, macierz);
	cout << endl;
    BellmanFord(wierzch_start, l_wierzch, macierz);
	

    system("pause");
}

void wyswietl_BellmanFord(int * koszt, int * numer, int l_wierzch, int wierzch_start)
{
	int * S = new int [l_wierzch];              // tymczasowy stos
    int sptr = 0;
	cout << "wyniki dla start: " << wierzch_start << endl;
	cout <<"End: " << " Dist: " <<  "Path: " << endl;
	for(int i=0; i<l_wierzch; i++)
	{
		cout.width(3);
		cout << i<< " |";
		cout.width(3);
		cout << koszt[i] <<"|   "; 

      for(int x = i; x!=-1; x = numer[x]) // umieszcz. wierzcholki na stosie
	  {
        S[sptr++] = x;            // w kolejności od ostatniego do pierwszego

      while(sptr)                 // drukujemy w kolejnosci od konca odl
        cout<< S[--sptr] << " "; // 
		
	  }
	  cout << endl;
	
	}
}
void BellmanFord(int wierzch_start, int l_wierzch,int ** macierz)
{
    int * koszt = new int[l_wierzch];    //koszt dojscia
    int * numer    = new int[l_wierzch];    //i-ty numer wierzcholka grafu
    for(int i=0; i<l_wierzch; i++)    //ktory jest poprzednikiem wierz. i-tego na 
    {                                //na najkrotszej sciezce        
        numer[i] = -1;		//p		 //domyslny numer
        koszt[i] = MAX;	//d		//dimyslny koszt dotarcia (nieskonczonosc)
    }
	koszt[wierzch_start]=0; //koszt dotarcia z wierzcholka startowego do startowego

	//teraz petla glowna
for(int i=1; i<=l_wierzch; i++)
{
	for(int w=0; w<l_wierzch; w++)
    {
        for(int k=0; k<l_wierzch; k++)
		{
		
			if((macierz[w][k] !=0) && (koszt[k]) >= (koszt[w]+ macierz[w][k]))
				{
					koszt[k] = koszt[w] + macierz[w][k];
					numer[k] = w;
					
				}
					
		}
	}
	
}	
wyswietl_BellmanFord(koszt, numer, l_wierzch, wierzch_start);
}


void wyswietl(int l_wierzch, int ** macierz)
{
for(int j=0; j<l_wierzch; j++)
    {
        cout << endl;
        for(int k=0; k<l_wierzch; k++)
            cout << setw(3) << macierz[j][k];
     }
	
}

Z góry dziękuję za odpowiedź.

Musisz wykonać jeszcze jedną pętlę wewnętrzną (po wszystkich krawędziach) w funkcji BellmanFord.

Jeśli będzie się dało wykonać jeszcze jakąś relaksację (tak to sie tłumaczy na polski?), to znaczy że graf zawiera cykl ujemny. Jeśli ani jedna nie zostanie wykonana, graf nie zawiera cyklu ujemnego.

PS. Swoją drogą Bellman Ford na macierzy sąsiedztwa IMO trochę mija się z celem, to już lepiej Floyda użyć.

Na szybko dodałem taką funkcję, która wykonuje się po wykonaniu funkcji BF, niestety zwraca false, a wiem że ten graf nie ma ujemnych cykli.

 bool sprawdz_uj_cykl(int l_wierzch, int **macierz, int *koszt, int* numer)
{
	for(int w=0; w<l_wierzch; w++)
        for(int k=0; k<l_wierzch; k++)
			if((macierz[w][k] !=0) && (koszt[k]) >= (koszt[w]+ macierz[w][k])) return false;
		return true;
	
}

Ps. domyślam że mija się z celem, lecz muszę zrobić ten algorytm na tej macierzy i potem jeszcze alg. Djisktry na tych samych danych.

No to dobrze zwraca. W czym problem? Jeśli nastąpi relaksacja to istnieje ujemny cykl i zwróci ci true.

Rzeczywiście, ale ze mnie gapa :F.
Dzięki za pomoc.