Algorytm Dijkstry

0

witam

Mam taki oto kod:

#include <iostream>
 using namespace std;
  
{
        int node;
        int weight;
        struct GRAF * next;
};
  
 int main()
{
      int m = 5;
  
      int FS[5][5];
  
       FS[1][1] = 0;
       FS[1][2] = 1;
       FS[1][3] = 1;
       FS[1][4] = 1;
       FS[1][5] = 1;
  
       FS[2][1] = 1;
       FS[2][2] = 0;
       FS[2][3] = 0;
       FS[2][4] = 1;
       FS[2][5] = 1;
  
       FS[3][1] = 1;
       FS[3][2] = 0;
       FS[3][3] = 0;
       FS[3][4] = 1;
       FS[3][5] = 1;
  
       FS[4][1] = 1;
       FS[4][2] = 1;
       FS[4][3] = 1;
       FS[4][4] = 0;
       FS[4][5] = 1;
       
       FS[5][1] = 1;
       FS[5][2] = 1;
       FS[5][3] = 1;
       FS[5][4] = 1;
       FS[5][5] = 0;
      
       int* d=new int[m];
       int* p=new int[m];
       bool* QS=new bool[m];
       struct GRAF **L=new struct GRAF*[m];
       struct GRAF* pw;
  
      int j,z;
  
       nt D[5][5];
       
       D[1][2] = 10;
       D[1][3] = 132;
       D[1][4] = 145;
       D[1][5] = 118;
  
       D[2][1] = 10;
       D[2][4] = 52;
       D[2][5] = 52;
  
       D[3][1] = 132;
       D[3][4] = 12;
       D[3][5] = 78;
  
       D[4][1] = 145;
       D[4][2] = 52;
       D[4][3] = 12;
       D[4][5] = 14;
       
       D[5][1] = 118;
       D[5][2] = 52;
       D[5][3] = 78;
       D[5][1] = 14;
  
  
       
       for(int i=1; i<=m; i++)
       {
             d[i] = 36544;  
             p[i] = 0;      
             QS[i] = false; 
             L[i] = NULL;  
       }
       int n = 0;
   
       
       for(int i=1; i<=m; i++)
       {
             
               for(int ie=1; ie<=m; ie++)
               {
                       
                       if(FS[i][ie]!=0)
                       {
                                if(i>n) n = i; if(ie>n) n = ie;
                                pw = new GRAF;
                                pw->next = L[i]; pw->node = ie;
                                pw->weight = z; L[i] = pw;
                       }
               }
       }
  
       
       d[1] = 0;
   
       for(int i=1; i<=n; i++)
       {
               int u = -1;
               for(j=1; j<=n; j++)
               {
                        if(!QS[j] && ((u == -1) || (d[j] < d[u]))) { u = j; }
               }
               QS[u] = true;
  
               pw = L[u];
               while(pw)
               {
                        if(!QS[pw->node] && (d[pw->node] > d[u] + pw->weight))
                        {
                                d[pw->node] = d[u] + pw->weight;
                                p[pw->node] = u;
                        }
                        pw = pw->next;
               }
        }
  
        system("CLS");
        int stos[5],ws;
  
        cout << "Graf o " << m << " wierzcholkach" << endl;
        cout << "------------------------" << endl << endl;
        
        
        for(int i=2; i<=n; i++)
        {
                cout << "Najkrotsza droga do wierzcholka " << i << " wynosi ";
                cout << d[i] << " przez wierzcholki : ";
  
                ws = 0; j = i;
                while(j){ stos[ws++] = j; j = p[j]; }
  
                while(ws) cout << stos[--ws] << ".";
                cout << endl;
         }
         
system("PAUSE");
}
 

Jednak kompiluje się i działa on tylko w Dev c++. W visualu 2008 wprawdzie kompilacja przebiega bezproblemowo, ale program zaraz po starcie wykrzacza się....gdzie leży problem?

0

Z tego co na pierwszy rzut oka widzę, to tworzysz tablicę o rozmiarze [5][5], a potem odwołujesz się do elementów o indeksach np [1][5]. Numerację elementów tablicy zaczyna się od 0, wiec mając tablicę o rozmiarze 5 możesz odwołać się do elementu o numerze 4 (piątego licząc od 0)

0

Niestety nadal nic:(

Powinno wyjść dokładnie takie coś:

http://imageshack.us/photo/my-images/197/11111111111w.jpg/

aby zgadzało się z tym:

http://imageshack.us/photo/my-images/121/222222222j.jpg/

w dev c++ wszystko przebiega idealnie...a w visualu nici....

0

oki, już mam:)
Wystarczyło zwiększyć rozmiar tablicy o 1.....ale nadal nie mam pojęcia czemu w devie działało, a w visualu nie:)

Pozdrtawiam

0

Dlatego, że wszędzie wychodzisz poza zakres tablicy.

0

Przydzielając pamięć w sposób char *c=new char[2];
Prawie na 100% dostaniesz obszar pamięci większy niż 2 baty, w zależności od kompilatora rozmiar zwróconego obszaru jest wielokrotnością jakieś potęgi dwójki np. 8, 16 itd.
gcc i kompilator visuala mają różną strategie przydzielania pamięci, więc prawdopodobnie przy ilościach 5x5 w gcc (Dev) nadal mieściłeś się w obszarze przydzielonym.

0 użytkowników online, w tym zalogowanych: 0, gości: 0