#include <string>
#include <iostream>
using namespace std;
struct Krawedz {
int s;
int t;
int w;
};
int *inicjalizujTabliceKosztowDojscia(int liczbaWierzcholkow, int poczatkowy) {
int *d = new int[liczbaWierzcholkow];
for (int i = 0; i < liczbaWierzcholkow; i++) d[i] = 999;
d[poczatkowy] = 0;
return d;
}
int *inicjalizujTablicePoprzednikow(int liczbaWierzcholkow) {
int *p = new int[liczbaWierzcholkow];
for (int i = 0; i < liczbaWierzcholkow; i++) p[i] = -1;
return p;
}
std::string formatValue(int value) {
char buffer[10];
if (value == 999) sprintf(buffer, "%5s", "oo");
else sprintf(buffer, "%5d", value);
return buffer;
}
void info(int *d, int *p, int liczbaWierzcholkow) {
std::string formattedW, formattedD, formattedP;
for (int i = 0; i < liczbaWierzcholkow; i++) {
formattedW.append(formatValue(i));
formattedD.append(formatValue(d[i]));
formattedP.append(formatValue(p[i]));
}
printf("w = [%s]\n", formattedW.c_str());
printf("d = [%s]\n", formattedD.c_str());
printf("p = [%s]\n\n\n", formattedP.c_str());
}
/**
* G = (V, E)
* @param V - liczba wierzchołków
* @param E - liczba krawędzi
* @param krawedzie - lista krawędzi
* @param poczatkowy - wyróżniony, początkowy wierzchołek
*/
void BellmanFordZListy(int V, int E, Krawedz *krawedzie, int poczatkowy) {
int *d = inicjalizujTabliceKosztowDojscia(V, poczatkowy); // [0, 999, 999, ...]
int *p = inicjalizujTablicePoprzednikow(V); // [-1, -1, -1, ...]
printf("\nStan początkowy:\n");
info(d, p, V);
// sprawdza wszystkie wierzcholki
for (int w = 0; w < V; w++) {
// sprawdza wszystkie krawedzie
for (int k = 0; k < E; k++) {
Krawedz krawedz = krawedzie[k];
if (d[krawedz.s] + krawedz.w < d[krawedz.t]) {
printf("\tKrawedz (%d, %d) = %d, d(s) = %d, d(t) = %d\n", krawedz.s, krawedz.t, krawedz.w, d[krawedz.s], d[krawedz.t]);
printf("\t\td(t): %d -> %d\n", d[krawedz.t], d[krawedz.s] + krawedz.w);
d[krawedz.t] = d[krawedz.s] + krawedz.w;
printf("\t\tp(t): %d -> %d\n", p[krawedz.t], krawedz.s);
p[krawedz.t] = krawedz.s;
}
}
printf("\nPo sprawdzeniu wierzcholka %d:\n", w);
info(d, p, V);
}
// bada czy występuje cykl ujemny
for (int k = 0; k < E; k++) {
Krawedz krawedz = krawedzie[k];
if (d[krawedz.s] + krawedz.w < d[krawedz.t]) {
printf("Cykl ujemy!\n");
return;
}
}
}
void BellmanFordZMacierzy(int V, int *macierz, int poczatkowy) {
int *d = inicjalizujTabliceKosztowDojscia(V, poczatkowy); // [0, 999, 999, ...]
int *p = inicjalizujTablicePoprzednikow(V); // [-1, -1, -1, ...]
printf("\nStan początkowy:\n");
info(d, p, V);
// sprawdza wszystkie wierzcholki
for (int w = 0; w < V; w++) {
// sprawdza wszystkie krawedzie
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// Krawedz krawedz = {i, j, macierz[i][j]};
Krawedz krawedz = {i, j, *(macierz+ i*V + j)};
if (d[krawedz.s] + krawedz.w < d[krawedz.t]) {
printf("\tKrawedz (%d, %d) = %d, d(s) = %d, d(t) = %d\n", krawedz.s, krawedz.t, krawedz.w, d[krawedz.s], d[krawedz.t]);
printf("\t\td(t): %d -> %d\n", d[krawedz.t], d[krawedz.s] + krawedz.w);
d[krawedz.t] = d[krawedz.s] + krawedz.w;
printf("\t\tp(t): %d -> %d\n", p[krawedz.t], krawedz.s);
p[krawedz.t] = krawedz.s;
}
}
}
printf("\nPo sprawdzeniu wierzcholka %d:\n", w);
info(d, p, V);
}
// bada czy występuje cykl ujemny
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// Krawedz krawedz = {i, j, macierz[i][j]};
Krawedz krawedz = {i, j, *(macierz+ i*V + j)};
if (d[krawedz.s] + krawedz.w < d[krawedz.t]) {
printf("Cykl ujemy!\n");
return;
}
}
}
}
int main() {
Krawedz krawedzie1[] = {
{0, 1, 5},
{1, 3, 3},
{1, 4, 9},
{2, 0, 3},
{2, 1, -4},
{3, 4, 3},
{3, 5, 2},
{4, 2, -1},
{4, 5, -5},
{5, 0, 9},
{5, 2, 8},
};
Krawedz krawedzie[] = {
{5, 3, 5},
{3, 2, 3},
{2, 0, 3},
{5, 4, 4},
{4, 1, 1},
{1, 0, 1},
{2, 1, -3},
{4, 2, -2}
};
int macierz[6][6] = {
// t=0 t=1 t=2 t=3 t=4 t=5
{999, 999, 999, 999, 999, 999}, // s=0
{ 1, 999, 999, 999, 999, 999}, // s=1
{ 3, -3, 999, 999, 999, 999}, // s=2
{999, 999, 3, 999, 999, 999}, // s=3
{999, 1, -2, 999, 999, 999}, // s=4
{999, 999, 999, 5, 4, 999}, // s=5
};
// BellmanFordZListy(6, std::size(krawedzie), krawedzie, 5);
BellmanFordZMacierzy(6, macierz[0], 5);
return 0;
}
Gdzie jest błąd?