/* Àëãîpèòì ïîèñêà äåpåâà êpàò÷àéøèõ ïóòåé âî âçâåøåííîì ãpàôå  */

/* Å.Äåéêñòpà 1959 ã.                                           */

#include <stdio.h>

#include <stdlib.h>

#include <float.h>

int load_matrix(int n, double* weigh);                                         /* Ââîä ìàòpèöû âåñîâ            */

int deik(int n, int s, double* weigh, int* Q, double* L);            /* Àëãîpèòì ïîèñêà                   */

void print(int n, int* Q, double* L);                                             /* Âûâîä påçóëüòàòà                   */

void main(void){

      int n=0,s=0,ret=0;

      double *weigh;

      int* Q;             /* Ìàññèâ ìåòîê óêàçàòåëåé íà ïpåäûäóùóþ âåpøèíó             */

      double* L;      /* Ìàññèâ íàéäåíûõ âåñîâ ïóòè äî âåpøèíû                               */

      printf("\nÀëãîpèòì ïîèñêà äåpåâà êpàò÷àéøèõ ïóòåé âî âçâåøåííîì ãpàôå.\n");

      printf("Å.Äåéêñòpà, 1959 ã.\n");

      printf("\nÂâåäèòå êîëè÷åñòâî âåpøèí..");

      scanf("%d",&n);

      if (n <= 1){

             printf("\nÊîëè÷åñòâî âåpøèí äîëæíî áûòü áîëüøå åäèíèöû!\n");

             exit(1);

      }

      printf("\nÂâåäèòå íà÷àëüíóþ âåpøèíó..");

      scanf("%d",&s);

      s--;

      if ((s < 0)||(s > (n-1))){

             printf("\nHà÷àëüíàÿ âåpøèíà óêàçàíà íåïpàâèëüíî!\n");

             exit(1);

      }

      Q=malloc(n*sizeof(int));

      L=malloc(n*sizeof(double));

      weigh=malloc(sizeof(double)*n*n);

      if ((weigh == NULL)||(Q == NULL)||(L == NULL)){

             printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ çàãpóçêè ìàññèâà!\n");

             exit(2);

      }

      ret=load_matrix(n,weigh);

      if (ret != 0){

             printf("\nÎøèáêà ââîäà äàííûõ!\n");

             exit(5);

      }

      ret=deik(n,s,weigh,Q,L);

      if (ret != 0){

             switch (ret){

                   case 1 :

                         printf("\nÃpàô íå ÿâëÿåòñÿ ñâÿçàííûì!\n");

                         exit(3);

                   case 2 :

                         printf("\nHåäîñòàòî÷íî ïàìÿòè äëÿ pàáîòû!\n");

                         exit(4);

             }

      }

      print(n,Q,L);

      free(weigh);

      free(Q);

      free(L);

}

int load_matrix(int n, double* weigh){

      int i,j,k;

      double tmp;

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

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

                   weigh[n*i+j]=(-1);

             }

      }

      printf("\nÂâåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.");

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

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

                   printf("\nÂåpøèíû %d è %d ",i+1,j+1);

                   k=scanf("%lf",&tmp);

                   if (k != 1){return(1);}

                   weigh[i*n+j]=tmp;

             }

      }

      return(0);

}

int deik(int n,int s, double* weigh, int* Q, double* L){

      int i,j,k;

      int* QI;            /* Ìàññèâ èíäèêàòîpîâ ïîñòîÿíñòâà ìåòîê óêàçàòåëåé */

      double tmp;

      QI=calloc(n,sizeof(int));

      if (QI == NULL){return(2);}

      QI[s]=1;

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

             Q[i]=(-1);

             L[i]=DBL_MAX;

      }

      Q[s]=s;

      L[s]=0;

      weigh[n*(n-1)+s]=0;

      for (k=0; k < n; k++){                    /* Îñíîâíîé öèêë ïî âåpøèíàì             */

             for (i=0; i < n; i++){                       /* Öèêë ïî ñòpîêàì ìàòpèöû âåñîâ */

                   for (j=i+1; j < n; j++){       /* Öèêë ïî ñòîëáöàì ìàòpèöû âåñîâ     */

             if ((QI[i]+QI[j] == 1)&&

                   (QI[i]*QI[j] == 0)&&

                   (weigh[i*n+j] != (-1.0))&&

                   (((QI[i] == 1)&&((L[i]+weigh[i*n+j]) < L[j]))||

                   ((QI[j] == 1)&&((L[j]+weigh[i*n+j]) < L[i])))){

                         if (QI[i] == 1){

                                L[j]=L[i]+weigh[i*n+j];

                                Q[j]=i;

                         }

                         else{

                                L[i]=L[j]+weigh[i*n+j];

                                Q[i]=j;

                         }

                   }

             }

      }

      for (tmp=DBL_MAX,i=0; i < n; i++){

             if ((tmp > L[i])&&(QI[i] == 0)){

                   tmp=L[i];

                   j=i;

             }

      }

      QI[j]=1;

      }

      free(QI);

      return(0);

}

void print(int n, int* Q, double* L){

      int i;

      printf("\n\nÄåpåâî êpàò÷àéøèõ ïóòåé:");

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

             printf("\nÂåpøèíà: %d  Ïpåäîê: %d  Âåñ: %5.2lf",i+1,Q[i]+1,L[i]);

      }

}

Òåñòîâûé ïðèìåð èç ðàáîòû [1] (ðèñ.8 íà ñòð. 12).

Àëãîpèòì ïîèñêà äåpåâà êpàò÷àéøèõ ïóòåé âî âçâåøåííîì ãpàôå.

Å.Äåéêñòpà, 1959 ã.

Ââåäèòå êîëè÷åñòâî âåpøèí.. 6

Ââåäèòå íà÷àëüíóþ âåpøèíó.. 6

Ââåäèòå ïîñëåäîâàòåëüíî âåñà påáåp äëÿ óêàçàííûõ âåpøèí èëè -1 äëÿ íåñìåæíûõ.

Âåpøèíû 1 è 2   2

Âåpøèíû 1 è 3  -1

Âåpøèíû 1 è 4   2

Âåpøèíû 1 è 5  -1

Âåpøèíû 1 è 6   5

Âåpøèíû 2 è 3   2

Âåpøèíû 2 è 4  -1

Âåpøèíû 2 è 5   2

Âåpøèíû 2 è 6  -1

Âåpøèíû 3 è 4  -1

Âåpøèíû 3 è 5  -1

Âåpøèíû 3 è 6   12

Âåpøèíû 4 è 5   1

Âåpøèíû 4 è 6   2

Âåpøèíû 5 è 6   5

Äåpåâî êpàò÷àéøèõ ïóòåé:

Âåpøèíà: 1  Ïpåäîê: 4  Âåñ:  4.00

Âåpøèíà: 2  Ïpåäîê: 5  Âåñ:  5.00

Âåpøèíà: 3  Ïpåäîê: 2  Âåñ:  7.00

Âåpøèíà: 4  Ïpåäîê: 6  Âåñ:  2.00

Âåpøèíà: 5  Ïpåäîê: 4  Âåñ:  3.00

Âåpøèíà: 6  Ïpåäîê: 6  Âåñ:  0.00

Òåñòîâûå ïðèìåðû:

Страницы: 1, 2, 3, 4, 5, 6, 7