Algorytm Bellmana-Forda

Question

#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];
     }
 
}

Działa poprawnie tylko dla dodatnic wartosci dla ujemnych wariuje ? Co zmienic lub dopisac ktoś pomoże?

Comments

Działa poprawnie tylko dla dodatnic wartosci dla ujemnych wariuje ?

Co znaczy "wariuje"? Masz zestaw przykładowych danych wejściowych i poprawnych danych wyjściowych?