#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?
