Witam,
mam problem z napisaniem dobrego algorytmu Dijkstra, chodzi mi o szybkość działania. Z góry przepraszam za to, że kod jest brzydki, nie miałem jak dotąd wiele doświadczeń z programowaniem, a już zwłaszcza w C++. Mam obraz monochromatyczny, tworzę zgrupowanie pikseli pomiędzy którymi przechodzenie ma zerową wagę (te wierzchołki są informacją wejściową). Wagi przejść pomiędzy wierzchołkami (pikselami) nie należącymi do tego zgrupowania są już niezerowe. Jako wyjście algorytmu chcę macierz wag, w której są najkrótsze ścieżki pomiędzy dowolnym wierzchołkiem, a dowolnym wierzchołkiem należącym do wspomnianego zgrupowania.
Niestety moja radosna twórczość działa bardzo wolno. Dużo czytałem o metodach przyspieszenia algorytmu Dijkstry, nie za bardzo umiem jednak z nimi ruszyć. Czy w moim kodzie są jakieś ewidentne fragmenty będące wąskim gardłem? Bardzo bym prosił o pomoc bo męczę się już z tym strasznie. Czy moglibyście mi polecić jakieś modyfikacje algorytmu, które poprawią wydajność? I ostatnie pytanie, czy napisanie tego z wykorzystaniem vector.h i kontenerów może tak radykalnie poprawić działanie? Nie chcę stosować transformacji odległościowej z OpenCV.
// struktury wykorzystywane w petli ponizej
struct indeks {
unsigned short szer;
unsigned short wys;
};
struct wsp_Q {
unsigned short x;
unsigned short y;
wsp_Q *next;
wsp_Q();
};
struct Q {
wsp_Q *poczatek;
void dodaj_element(int, int);
void usun_element();
void usun_element1(unsigned short, unsigned short);
void usun(wsp_Q *, wsp_Q *);
void pokaz_liste();
Q();
};
// metoda za pomoca ktorej usuwam element (wierzcholek) z listy Q_t
void Q::usun(wsp_Q *p1, wsp_Q *p_p1) {
wsp_Q *temp, *temp2;
temp = p1;
temp2 = p_p1;
if (temp == poczatek)
poczatek = temp->next;
else
temp2->next = temp->next;
delete temp;
}
// ...
// newralgiczny fragment kodu
// lista wierzcholkow to Q_t
while (Q_t->poczatek != NULL)
{
// usuniecie wierzcholka aktualnie analizowanego, metoda przyjmuje jako pierszy argument wskaznik na strukture wsp_Q dla wierzcholka:
// p_najm - aktualnie rozpoatrywany, p_najm_p - poprzedni na liscie w stosunu do aktualnie rozpatrywanego
Q_t->usun(p_najm, p_najm_p);
// indeksy wierzcholkow bedacych sasiadami dla aktualnie rozpoatrywanego wierzcholka, sasiad to statyczna tablica struktur - indeks
// temp_element zawiera indeksy aktualnie rozpatrywanego wierzcholka - struktura "indeks"
sasiad[0].wys = temp_element.wys - 1;
sasiad[0].szer = temp_element.szer;
sasiad[1].wys = temp_element.wys - 1;
sasiad[1].szer = temp_element.szer + 1;
sasiad[2].wys = temp_element.wys;
sasiad[2].szer = temp_element.szer + 1;
sasiad[3].wys = temp_element.wys + 1;
sasiad[3].szer = temp_element.szer + 1;
sasiad[4].wys = temp_element.wys + 1;
sasiad[4].szer = temp_element.szer;
sasiad[5].wys = temp_element.wys + 1;
sasiad[5].szer = temp_element.szer - 1;
sasiad[6].wys = temp_element.wys;
sasiad[6].szer = temp_element.szer - 1;
sasiad[7].wys = temp_element.wys - 1;
sasiad[7].szer = temp_element.szer - 1;
// ograniczenie grafu - wierzcholki graniczne nie beda rozpatrywane
if (temp_element.wys != 0 && temp_element.wys != img_ycrcb.rows - 1 && temp_element.szer != 0 && temp_element.szer != img_ycrcb.cols - 1)
{
// dodawanie do listy Q_t nowych wierzcholkow
// D_w to dynamiczna tablica, dla danego zestawu Q_t poczatkowego wartosc "k" (pierwszy wymiar) jest stala
if (D_w[k][temp_element.wys][temp_element.szer] + W1[temp_element.wys][temp_element.szer] < D_w[k][sasiad[0].wys][sasiad[0].szer])
{
D_w[k][sasiad[0].wys][sasiad[0].szer] = D_w[k][temp_element.wys][temp_element.szer] + W1[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[0].wys, sasiad[0].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W2[temp_element.wys][temp_element.szer] < D_w[k][sasiad[1].wys][sasiad[1].szer])
{
D_w[k][sasiad[1].wys][sasiad[1].szer] = D_w[k][temp_element.wys][temp_element.szer] + W2[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[1].wys, sasiad[1].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W3[temp_element.wys][temp_element.szer] < D_w[k][sasiad[2].wys][sasiad[2].szer])
{
D_w[k][sasiad[2].wys][sasiad[2].szer] = D_w[k][temp_element.wys][temp_element.szer] + W3[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[2].wys, sasiad[2].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W4[temp_element.wys][temp_element.szer] < D_w[k][sasiad[3].wys][sasiad[3].szer])
{
D_w[k][sasiad[3].wys][sasiad[3].szer] = D_w[k][temp_element.wys][temp_element.szer] + W4[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[3].wys, sasiad[3].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W5[temp_element.wys][temp_element.szer] < D_w[k][sasiad[4].wys][sasiad[4].szer])
{
D_w[k][sasiad[4].wys][sasiad[4].szer] = D_w[k][temp_element.wys][temp_element.szer] + W5[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[4].wys, sasiad[4].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W6[temp_element.wys][temp_element.szer] < D_w[k][sasiad[5].wys][sasiad[5].szer])
{
D_w[k][sasiad[5].wys][sasiad[5].szer] = D_w[k][temp_element.wys][temp_element.szer] + W6[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[5].wys, sasiad[5].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W7[temp_element.wys][temp_element.szer] < D_w[k][sasiad[6].wys][sasiad[6].szer])
{
D_w[k][sasiad[6].wys][sasiad[6].szer] = D_w[k][temp_element.wys][temp_element.szer] + W7[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[6].wys, sasiad[6].szer);
}
if (D_w[k][temp_element.wys][temp_element.szer] + W8[temp_element.wys][temp_element.szer] < D_w[k][sasiad[7].wys][sasiad[7].szer])
{
D_w[k][sasiad[7].wys][sasiad[7].szer] = D_w[k][temp_element.wys][temp_element.szer] + W8[temp_element.wys][temp_element.szer];
Q_t->dodaj_element(sasiad[7].wys, sasiad[7].szer);
}
}
// wybranie wierzcholka o najmniejszej wartosci macierzy D_w
// p,p_p,p_najm,p_najm_p to wskazniki na struktury wsp_Q
if (Q_t->poczatek != NULL)
{
p = Q_t->poczatek;
p_p = NULL;
p_najm = p;
p_najm_p = NULL;
temp_element.szer = Q_t->poczatek->x;
temp_element.wys = Q_t->poczatek->y;
// przeszukanie listy w celu znalezienia wskaznika na element najlepiej rokujacy (najmniejsza wartosci D_w)
while (p->next != NULL)
{
// macierz D_w zawiera aktualne wartosci energetyczne sciezki dla danego wierzcholka
if (D_w[k][p->y][p->x] < D_w[k][temp_element.wys][temp_element.szer])
{
temp_element.szer = p->x;
temp_element.wys = p->y;
p_najm = p;
p_najm_p = p_p;
}
p_p = p;
p = p->next;
}
}