SHARE
TWEET

Untitled

a guest Jan 21st, 2020 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Vertices {
  2.     string name;
  3.     list vertices;
  4.     Vertices * next;
  5. };
  6.  
  7. struct listofString {
  8.     string name;
  9.     listofString *next;
  10. };
  11.  
  12. struct vertinfo {
  13.     string name;
  14.     int koszt;
  15.     listofString *visited;
  16. };
  17.  
  18. /*Na poczatku musisz miec wypelnione Tab wierzcholkami i odleglosciami (wierzcholek poczatkowy ma miec odleglosc 0
  19. pusta liste poprzednikow a reszta nieskonczonosc i tez pusta liste poprzednikow). Wywolujac funkcje koszt ustawiasz na
  20. 0 i poprzednicy to pusta lista*/
  21. void dijkstra(Vertices *&S, listofString *&Q, vertinfo *&Tab, string vert, int koszt, listofString poprzednicy) {
  22.     dodajnapoczatek(poprzednicy, vert); // dodajesz na poczatek aktualny wierzcholek do listy poprzednikow
  23.     dodajnapoczatek(Q, vert)// to samo tylko ze do listy Q (lista Q jest podana referencyjnie takze niezaleznie dla wszystkich wierzcholkow jest taka sama w sensie nie tak jak poprzednicy gdzie dla kazdej galezi rekurencji jest inna)
  24.     listaSasiadowzodleglosciami *sasiedzi = getNeighbours(S, vert);//pobierz liste sasiadow wierzcholka vert
  25.     while (sasiedzi) {
  26.         if (!sprawdzCzyJestWOdwiedzonych(sasiedzi->city, Q)) { //sprawdzasz czy jest w liscie Q jesli tak to nic se nei robisz
  27.             int kosztsasiadaZtabeli = pobierzkoszt(Tab, sasiedzi->city); // pobierasz koszt z tej listy co tobie mowilem z trzema argumentami
  28.             if (koszt + odleglosc(sasiedzi->city) < kosztsasiadaZtabeli) { //no jesli ten koszt jest wiekszy niz droga ktora dotarles do tego wierzcholka to
  29.                 Ustawnowykoszt(Tab, sasiedzi->city, koszt + odleglosc); // zastap ten koszt nowym
  30.                 usun(Tab->poprzednicy); //usun wszystkich poprzednikow
  31.                 tab -> poprzednicy = poprzednicy; //zastap poprzednikow z tabeli nowymi
  32.                 dijkstra(S, Q, Tab, sasiedzi->city, koszt + odleglosc(sasiedzi->city, poprzednicy);//rekurencyjnie wywolaj funkcje dla nowego wierzcholka
  33.  
  34.  
  35.             }
  36.         }
  37.         sasiedzi = sasiedzi->next
  38.     }
  39. }
  40. //funkcja nic nie zwraca ale zmienia ci poprzez referencje masz ustawiona tabele Tab i wystarczy pobrac z tej tabeli dla wierzcholka porządanego jego koszt i poprzednikow
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top