Witam, mam za zadanie zaimplementować algorytm 1,5 przybliżony komiwojazera i nie mogę ruszyć już na samym początku, robię drzewo spinające algorytmem Prima. Po wpisaniu wszystkich danych dotyczących grafu np. dla grafu 3 wierzchołkowego i 3 połączeń o dowolnych wagach, wysypuje się przy minimum globalnym. Może ktoś spojrzy świeżym okiem i zauważy coś niepokojącego...bo przez to algorytm liczy, ale niepoprawnie.
#include <iostream>
using namespace std;
struct miasto{ char nazwa; int lpol; double *odle; miasto **gdzie; };
struct minimalna_krawedz{ int i; int j; };
struct minimum{ int i; int j; double krawedz; };
char sprawdz(miasto **miasta, int lmiast, char nazw){
int i = 0;
for (i = 0; i<lmiast; ++i){
if (miasta[i]->nazwa == nazw) {
cout << "Znalazlem miasto o takiej nazwie!!!" << endl;
return 0;
}
}
return 1;
}
int sprawdz_wolne_linki(miasto *miasta){
int i = 0;
for (i = 0; i<miasta->lpol; i++)
if (miasta->gdzie[i] == NULL) return 0;
return 2;
}
int sprawdz_wskazanie(miasto *miasta1, miasto *miasta2){
int i = 0;
for (i = 0; i<miasta1->lpol; i++)
if (miasta1->gdzie[i] == miasta2) return 1;
return 0;
}
int szukaj(miasto **miasta, int lmiast, int k){
char nazw;
int i = 0, j = 0, b = 0;
do{
cin >> nazw;
for (i = 0; i<lmiast; ++i){
if (miasta[i]->nazwa == nazw){
if (sprawdz_wskazanie(miasta[i], miasta[k]) == 1) b = 1;
else if (sprawdz_wolne_linki(miasta[i]) == 2) b = 2;
else{
cout << "Znalazlem miasto o takiej nazwie!!!" << endl;
return i;
}
}
}
if (b == 1)
cout << "Blad!!! Juz istnieje takie polaczenie z tym miastem !!!\nPodaj prawidlowa nazwe miasta" << endl;
else if (b == 2)
cout << "Blad!!! Nie moge tam sie podpiac !!!\nPodaj prawidlowa nazwe miasta" << endl;
else
cout << "Blad!!! Niema takiego miasta !!!\nPodaj prawidlowa nazwe miasta" << endl;
} while (1);
}
miasto *dodaj(miasto *P, int lmiast, miasto **miasta, int i){
int ii = 0, jj = 0, k = 0;
P = new miasto;
cout << "Podaj nazwe miasta" << endl;
do{
cin >> P->nazwa;
if (sprawdz(miasta, i, P->nazwa)){
jj = 1;
cout << "Podaj liczbe polaczen dla " << P->nazwa << endl;
do{
cin >> P->lpol;
if (P->lpol<lmiast){
P->odle = new double[P->lpol];
P->gdzie = new miasto*[P->lpol];
for (k = 0; k<P->lpol; ++k)
P->gdzie[k] = NULL;
ii = 1;
}
else
cout << "Blad!!!\nPodaj poprawna ilosc polaczen\n";
} while (ii == 0);
}
else
cout << "Blad!!! Takie miasto juz istnieje\nPodaj poprawna nazwe miasta\n";
} while (jj == 0);
return P;
}
void link(miasto *miasta, miasto *link, int j, double odlegl){
int i = 0;
for (i = j; i<miasta->lpol; ++i){
if (miasta->gdzie[i] == NULL){
miasta->gdzie[i] = link;
miasta->odle[i] = odlegl;
break;
}
}
}
void laczenie(miasto **miasta, int lmiast){
int ii, i = 0, j = 0;
for (i = 0; i<lmiast; i++)
for (j = 0; j<miasta[i]->lpol; j++){
if (miasta[i]->gdzie[j] == NULL){
cout << "Miasto " << miasta[i]->nazwa << " laczymy z ??\n";
do{
ii = szukaj(miasta, lmiast, i);
if (i == ii) cout << "blad!!! \nPodaj prawidlowa nazwe miasta" << endl;
} while (i == ii);
cout << "Podaj odleglosc z " << miasta[i]->nazwa << " do " << miasta[ii]->nazwa << endl;
double odlegl;
cin >> odlegl;
link(miasta[i], miasta[ii], j, odlegl);
link(miasta[ii], miasta[i], 0, odlegl);
}
}
}
void rysuj(miasto **miasta, int lmiast){
int i = 0, j = 0;
cout << "Mamy takie miasta:\n";
for (i = 0; i<lmiast; ++i)
cout << miasta[i]->nazwa << endl;
for (i = 0; i<lmiast; ++i){
cout << "Miasto: " << miasta[i]->nazwa << " ma polaczenie do \n";
for (j = 0; j<miasta[i]->lpol; j++)
cout << miasta[i]->gdzie[j]->nazwa << " na odleglosc " << miasta[i]->odle[j] << endl;
}
}
miasto **tworzenie(miasto **miasta, int lmiast){
if (lmiast>1){
miasta = new miasto*[lmiast];
int i = 0;
for (i = 0; i<lmiast; ++i)
miasta[i] = dodaj(miasta[i], lmiast, miasta, i);
laczenie(miasta, lmiast);
}
else
cout << "Blad!!!" << endl;
return miasta;
}
minimalna_krawedz przeszukaj_mimalnej_krawedzi(miasto **miasta, int lmiast){
int i = 0, j = 0;
minimalna_krawedz min;
double temp = miasta[0]->odle[0];
min.i = 0;
min.j = 0;
for (i = 0; i<lmiast; ++i){
for (j = 0; j<miasta[i]->lpol; ++j)
if (miasta[i]->odle[j]<temp){
temp = miasta[i]->odle[j];
min.i = i;
min.j = j;
}
}
return min;
}
int wskaznik(char nazwa, miasto **miasta, int lmiast)
{
int i = 0;
for (i = 0; i < lmiast; i++){
if (nazwa == miasta[i]->nazwa) return i;
}
}
int porownaj(miasto *zrodlo1, miasto **miasta2, int licznik)
{
int i = 0;
for (i = 0; i<licznik; ++i)
if (miasta2[i] == zrodlo1) return 0;
return 1;
}
minimum znajdz_minimum(miasto *zrodlo1, miasto **miasta, int lmiast, miasto **miasta2, int licznik){
minimum min;
int i = 0, j = 0;
min.krawedz = -1;
min.i = -1;
min.j = -1;
//wybieramy losowy wskaznik
for (i = 0; i<zrodlo1->lpol; i++){
if (porownaj(zrodlo1->gdzie[i], miasta2, licznik)){
min.krawedz = zrodlo1->odle[i];
min.i = wskaznik(zrodlo1->nazwa, miasta, lmiast);
min.j = i;
}
}
for (i = 0; i<zrodlo1->lpol; i++){
if ((zrodlo1->odle[i]<min.krawedz) && (porownaj(zrodlo1->gdzie[i], miasta2, licznik))){
min.krawedz = zrodlo1->odle[i];
min.i = wskaznik(zrodlo1->nazwa, miasta, lmiast);
min.j = i;
}
}
return min;
}
int dodajmiasta(miasto **miasta2, miasto *nowe, int lmiast){
static int i = 0;
if (i<lmiast){
miasta2[i] = nowe;
i++;
}
return i;
}
minimum minimum_globalne(minimum *x, int licznik)
{
minimum min;
int i = 0;
min.i = -1;
for (i = 0; i<licznik; i++)
if (x[i].i != -1){
min = x[i];
break;
}
for (i = 0; i<licznik; i++){
if ((x[i].krawedz<min.krawedz) && (x[i].i != -1))
min = x[i];
}
return min;
}
void wyswietl(minimalna_krawedz mink, miasto **miasta, int lmiast, miasto **miasta2){
minimum *x, x1;
static double mindroga = 0;
static int k = 0;
int licznik;
mindroga = mindroga + miasta[mink.i]->odle[mink.j];
if (k == 0){
cout << "|" << miasta[mink.i]->nazwa;
cout << miasta[mink.i]->gdzie[mink.j]->nazwa << "|=";
cout << miasta[mink.i]->odle[mink.j] << "\n";
licznik = dodajmiasta(miasta2, miasta[mink.i], lmiast);
licznik = dodajmiasta(miasta2, miasta[mink.i]->gdzie[mink.j], lmiast);
x = new minimum[licznik];
}
else{
cout << "|" << miasta[mink.i]->nazwa;
cout << miasta[mink.i]->gdzie[mink.j]->nazwa << "|=";
cout << miasta[mink.i]->odle[mink.j] << "\n";
licznik = dodajmiasta(miasta2, miasta[mink.i]->gdzie[mink.j], lmiast);
x = new minimum[licznik];
}
int i = 0;
for (i = 0; i<licznik; ++i)
x[i] = znajdz_minimum(miasta2[i], miasta, lmiast, miasta2, licznik);
x1 = minimum_globalne(x, licznik);
mink.i = x1.i;
mink.j = x1.j;
k++;
if (x1.i != -1)
wyswietl(mink, miasta, lmiast, miasta2);
else{
cout << "\n";
cout << "Minimalna droga wynosi " << mindroga << endl;
}
}
void main(){
miasto **miasta = NULL;
minimalna_krawedz mink;
cout << "Podaj liczbe miast" << endl;
int lmiast = 4;
cin >> lmiast;
miasto **miasta2;
miasta2 = new miasto*[lmiast];
miasta = tworzenie(miasta, lmiast);
rysuj(miasta, lmiast);
mink = przeszukaj_mimalnej_krawedzi(miasta, lmiast);
cout << "Minimalne drzewo!!! :" << endl;
wyswietl(mink, miasta, lmiast, miasta2);
}