Программная реализация алгоритма Дейкстры

}

}

//============================================================

int dextra (int **vertex, int *flag, int *len, int n, int xk, int p)

{

int i, j;

 

for(i = 1; i <= n; i++)

{

itoa(1, s, 100);

strcpy(path[i], "X");

strcat(path[i], s);

}

 

do

{

 for(i = 0; i < n; i++)

  if((vertex[p][i] != 65535) && (!*(flag + i)) && (i != p))

  {

   if(*(len + i) > *(len + p) + vertex[p][i])

   {

    itoa(i+1, s, 100);

strcpy(path[i+1], path[p + 1]);

strcat(path[i+1], "-X");

strcat(path[i+1], s);

   }

   *(len + i) = *(len + i) < (*(len + p) + vertex[p][i]) ? *(len + i) : (*(len + p) + vertex[p][i]);

  }

 

for(i = 0; i < n; i++)

if(!*(flag + i)) p = i;

for(i = 0; i < n; i++)

if((*(len + p) > *(len + i)) && (!*(flag + i))) p = i;

 

*(flag + p) = 1;

}while(p != xk);

 

return p;

}

//==================================================================

void main (int argc, char *argv[])

{

int  i, j;   // kounters

int  n, p;   // vertex count

int  xn, xk; // start and end points

 

cout << "Enter nuber of vertexes: "; // entering number of vertexes

cin  >> n;

 

if ((n > 65536) || (n <= 1))

    {

cout << "Vrong input" << endl;

_getch ();

 return;

}

 

cout << endl;

 

int *len  = new int [n];    // new arrays lanth of way

int *flag = new int [n];    // flag check or not

 

    int **vertex = new int *[n];   // matrix of ways

 for (i = 0; i < n; i++)    //

  vertex[i] = new int [n];    //

 

for (i = 0; i < n; i++)     // init matrix

for (j = 0; j < n; j++)    //

vertex[i][j] = 0;    //

 

if (!scan_matr(vertex, n))    // enter ways

return;        //

// 

print_matr (vertex, n);     // print matryx of ways

null_matr  (vertex, n);     // 0 <- 65536 max value

 

cout << "Start point: ";    // enter start pint

cin  >> xn;        //

if ((xn > 65536) || (xn <= 0))   //

    {          //

cout << "Vrong input" << endl;   //

_getch ();        //

 return;        //

}          //

 

cout << "End   point: ";    // enter end point

cin  >> xk;        //

if ((xk > 65536) || (xk <= 0))

    {

cout << "Vrong input" << endl;

_getch ();

 return;

}

 

cout << endl;

 

xk--;         //

xn--;         // array starts from 0 -> ;)))

 

if(xn == xk)       // compare start point and end point

{          //

cout << "No way to run, no way to go..." << endl;  // the points are same

_getch();       //

return;        //

}          //

 

for(i = 0; i < n; i++)     // clearing flags

{          // lenth = 65536

flag[i] = 0;      //

len[i]  = 65535;     //

}          //

 

len[xn]  = 0;        //

flag[xn] = 1;        //

p = dextra (vertex, flag, len, n, xk, xn); // Dextra algorithm

 

//------------------------------output all information---------------------------------------- 

if(len[p] != 65535)

{

ofstream out ("Result.txt",ios::out);

out.clear();

out << "Way: " << path[p + 1]  << endl;

out << "Way lenth: " << len[p] << endl;

 

cout << "Way: " << path[p + 1]  << endl;

cout << "Way lenth: " << len[p] << endl;

out.close();

}

else

cout<<"no such way!"<<endl;

 

_getch();

 

delete vertex;

delete len;

delete flag;

}

Приложение Б

Окно консоли